-
Notifications
You must be signed in to change notification settings - Fork 2
/
LRU_cache.h
44 lines (40 loc) · 1.49 KB
/
LRU_cache.h
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
/*
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
*/
class LRUCache{
public:
/***********************website ***************************************/
LRUCache(int capacity) : size(capacity) {}
int get(int key) {
auto it = table.find(key);
if (it == table.cend()) { return -1; }
move_to_front(it);
return it->second.second;
}
void set(int key, int value) {
auto it = table.find(key);
if (it != table.cend()) {
it->second.second = value;
move_to_front(it);
return;
}
if (table.size() == size) {
table.erase(lru_data.back());
lru_data.pop_back();
}
lru_data.emplace_front(key);
table[key] = {lru_data.begin(), value};
}
private:
typedef unordered_map<int, pair<typename list<int>::iterator, int> > Table;
list<int> lru_data;
Table table;
int size;
void move_to_front(const typename Table::iterator& it) {
lru_data.erase(it->second.first);
lru_data.emplace_front(it->first);
it->second.first = lru_data.begin();
}
};