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