1 /* 2 * File: lrucache.hpp 3 * Author: Alexander Ponomarev 4 * 5 * Created on June 20, 2013, 5:09 PM 6 */ 7 8 #ifndef _LRUCACHE_HPP_INCLUDED_ 9 #define _LRUCACHE_HPP_INCLUDED_ 10 11 #include <map> 12 #include <list> 13 #include <cstddef> 14 #include <stdexcept> 15 16 #include "optional.hpp" 17 18 namespace cache { 19 20 template<typename key_t, typename value_t> 21 class lru_cache { 22 public: 23 typedef typename std::pair<key_t, value_t> key_value_pair_t; 24 typedef typename std::list<key_value_pair_t>::iterator list_iterator_t; 25 lru_cache(size_t max_size)26 lru_cache(size_t max_size) : 27 _max_size(max_size) { 28 } 29 put(const key_t & key,const value_t & value)30 void put(const key_t& key, const value_t& value) { 31 auto it = _cache_items_map.find(key); 32 _cache_items_list.push_front(key_value_pair_t(key, value)); 33 if (it != _cache_items_map.end()) { 34 _cache_items_list.erase(it->second); 35 _cache_items_map.erase(it); 36 } 37 _cache_items_map[key] = _cache_items_list.begin(); 38 39 if (_cache_items_map.size() > _max_size) { 40 auto last = _cache_items_list.end(); 41 last--; 42 _cache_items_map.erase(last->first); 43 _cache_items_list.pop_back(); 44 } 45 } 46 get(const key_t & key)47 nonstd::optional<value_t> get(const key_t& key) { 48 auto it = _cache_items_map.find(key); 49 if (it == _cache_items_map.end()) { 50 return nonstd::nullopt; 51 } 52 53 _cache_items_list.splice(_cache_items_list.begin(), _cache_items_list, it->second); 54 return it->second->second; 55 } 56 exists(const key_t & key) const57 bool exists(const key_t& key) const { 58 return _cache_items_map.find(key) != _cache_items_map.end(); 59 } 60 size() const61 size_t size() const { 62 return _cache_items_map.size(); 63 } 64 set_max_size(size_t max_size)65 void set_max_size(size_t max_size) { 66 this->_max_size = max_size; 67 } 68 clear()69 void clear() { 70 this->_cache_items_map.clear(); 71 this->_cache_items_list.clear(); 72 } 73 74 private: 75 std::list<key_value_pair_t> _cache_items_list; 76 std::map<key_t, list_iterator_t> _cache_items_map; 77 size_t _max_size; 78 }; 79 80 } // namespace cache 81 82 #endif /* _LRUCACHE_HPP_INCLUDED_ */ 83 84