LRU Cache

LRU Cache

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
#include <iostream>
#include <list>
#include <unordered_map>
using std::list;
using std::unordered_map;
struct CacheItem {
int key;
int value;
CacheItem(int k, int val) : key(k), value(val) { }
};
class LRUCache {
public:
LRUCache(int capacity) : m_capacity(capacity) {
}
int get(int key) {
if (m_map.find(key) != m_map.end()) {
moveToHead(key);
return m_map[key]->value;
}
return -1;
}
void set(int key, int value) {
if (m_map.find(key) != m_map.end()) {
m_map[key]->value = value;
moveToHead(key);
} else {
if (m_cache.size() == m_capacity) {
m_map.erase(m_cache.back().key);
m_cache.pop_back();
}
CacheItem CacheItem(key, value);
m_cache.push_front(CacheItem);
m_map[key] = m_cache.begin();
}
}
private:
void moveToHead(int key) {
CacheItem updateCacheItem = *m_map[key];
m_cache.erase(m_map[key]);
m_cache.push_front(updateCacheItem);
m_map[key] = m_cache.begin();
}
int m_capacity;
list<CacheItem> m_cache;
unordered_map<int, list<CacheItem>::iterator> m_map;
};
int main() {
LRUCache cache(2);
cache.set(1, 11);
cache.set(2, 22);
std::cout << cache.get(1) << std::endl;
cache.set(3, 33);
std::cout << cache.get(2) << std::endl;
cache.set(4, 44);
std::cout << cache.get(1) << std::endl;
std::cout << cache.get(3) << std::endl;
std::cout << cache.get(4) << std::endl;
return 0;
}