/
146.lru-cache.cpp
62 lines (56 loc) · 1.52 KB
/
146.lru-cache.cpp
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
/*
* @lc app=leetcode id=146 lang=cpp
*
* [146] LRU Cache
*/
// @lc code=start
class LRUCache
{
int capacity_;
//* we keep the back node as the most recently used
list<int> cache; //* O(1) remove + O(1) add to back
unordered_map<int, list<int>::iterator> key2itr; //* allows use to access node in linked list in O(1)
unordered_map<int, int> key2val; //* from key to val in O(1) time
public:
LRUCache(int capacity) : capacity_(capacity) {}
int get(int key)
{
if (key2val.find(key) == key2val.end())
return -1;
auto itr = key2itr[key];
int val = key2val[key];
cache.erase(itr);
cache.push_back(key);
key2itr[key] = prev(cache.end());
return val;
}
void put(int key, int value)
{
if (this->get(key) != -1)
{
key2val[key] = value;
}
else
{
if (key2itr.size() == capacity_)
{
int LRUkey = *cache.begin();
key2val.erase(LRUkey);
cache.erase(cache.begin());
key2itr.erase(LRUkey);
}
cache.push_back(key);
key2val[key] = value;
key2itr[key] = prev(cache.end());
}
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
// @lc code=end
// key4 ... key7 key3 key2 key8 end
//