blob: 3279b356ebe57883a8fae018b909772dbe5d7315 (
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
|
// -*- mode: c++; c-basic-offset: 2; -*-
#ifndef LRU_HH
#define LRU_HH
#include <algorithm>
#include <deque>
#include <unordered_map>
template<typename K, typename V>
class lru {
public:
lru(size_t size)
: size_(size) {
}
bool empty() const {
return usage_.empty();
}
size_t size() const {
return usage_.size();
}
V* get(K const& key) {
auto it = data_.find(key);
if (it == data_.end()) return nullptr;
auto it2 = std::find(usage_.begin(), usage_.end(), key);
if (it2 != usage_.begin()) {
usage_.erase(it2);
usage_.push_front(key);
}
return &it->second;
}
void insert(K const& key, V const& data) {
auto pair = data_.insert(std::make_pair(key, data));
if (pair.second) {
usage_.push_front(key);
shrink_to_size();
} else {
pair.first->second = data;
auto it = std::find(usage_.begin(), usage_.end(), key);
if (it != usage_.begin()) {
usage_.erase(it);
usage_.push_front(key);
}
}
}
void erase(K const& key) {
if (data_.erase(key)) {
usage_.erase(std::find(usage_.begin(), usage_.end(), key));
}
}
private:
void shrink_to_size() {
if (usage_.size() > size_) {
data_.erase(usage_.back());
usage_.pop_back();
}
}
size_t const size_;
std::deque<K> usage_;
std::unordered_map<K, V> data_;
};
#endif // LRU_HH
|
