Fleet  0.0.9
Inference in the LOT
LRUCache.h
Go to the documentation of this file.
1 /*
2  * File: lrucache.hpp
3  * Author: Alexander Ponomarev
4  *
5  * Created on June 20, 2013, 5:09 PM
6  */
7 
8 
9 // https://github.com/lamerman/cpp-lru-cache
10 
11 #ifndef _LRUCACHE_HPP_INCLUDED_
12 #define _LRUCACHE_HPP_INCLUDED_
13 
14 #include <unordered_map>
15 #include <list>
16 #include <cstddef>
17 #include <stdexcept>
18 
19 namespace cache {
20 
21 template<typename key_t, typename value_t>
22 class lru_cache {
23 public:
24  typedef typename std::pair<key_t, value_t> key_value_pair_t;
25  typedef typename std::list<key_value_pair_t>::iterator list_iterator_t;
26 
27  lru_cache(size_t max_size) :
28  _max_size(max_size) {
29  }
30 
31  void put(const key_t& key, const value_t& value) {
32  auto it = _cache_items_map.find(key);
33  _cache_items_list.push_front(key_value_pair_t(key, value));
34  if (it != _cache_items_map.end()) {
35  _cache_items_list.erase(it->second);
36  _cache_items_map.erase(it);
37  }
38  _cache_items_map[key] = _cache_items_list.begin();
39 
40  if (_cache_items_map.size() > _max_size) {
41  auto last = _cache_items_list.end();
42  last--;
43  _cache_items_map.erase(last->first);
44  _cache_items_list.pop_back();
45  }
46  }
47 
48  const value_t& get(const key_t& key) {
49  auto it = _cache_items_map.find(key);
50  if (it == _cache_items_map.end()) {
51 
52  throw std::range_error("There is no such key in cache");
53  } else {
54  _cache_items_list.splice(_cache_items_list.begin(), _cache_items_list, it->second);
55  return it->second->second;
56  }
57  }
58 
59  bool exists(const key_t& key) const {
60  return _cache_items_map.find(key) != _cache_items_map.end();
61  }
62 
63  size_t size() const {
64  return _cache_items_map.size();
65  }
66 
67 private:
68  std::list<key_value_pair_t> _cache_items_list;
69  std::unordered_map<key_t, list_iterator_t> _cache_items_map;
70  size_t _max_size;
71 };
72 
73 } // namespace cache
74 
75 #endif /* _LRUCACHE_HPP_INCLUDED_ */
std::list< key_value_pair_t >::iterator list_iterator_t
Definition: LRUCache.h:25
Definition: LRUCache.h:22
bool exists(const key_t &key) const
Definition: LRUCache.h:59
std::pair< key_t, value_t > key_value_pair_t
Definition: LRUCache.h:24
size_t size() const
Definition: LRUCache.h:63
lru_cache(size_t max_size)
Definition: LRUCache.h:27
void put(const key_t &key, const value_t &value)
Definition: LRUCache.h:31
Definition: LRUCache.h:19