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.
?
?
?
?
?
?
分析
1：维护最近最少（LRU）使用的cache
?
1）使用count计数，每次操作cache时（get、set），该cache的count置0，其余cache的count加1，count最大的为最近最少使用的cache
?
? ? ? 2）使用链表，每次操作cache时（get、set），将该cache移动至链表头，链表尾的cache为最近最少使用的cache
?
2：快速查找cache
?
1）使用stl::unordered_map存储cache地址（内部hashTable）
?
?
?
版本一
使用std::list维护LRU，链表中存储cache实际空间。Runtime: 248ms。
?
?
?1 #include
?2 #include
?3?
?4 struct KeyValue {
?5 ? ? KeyValue(int pKey, int pValue):key(pKey), value(pValue) {};
?6 ? ? int key;
?7 ? ? int value;
?8 };
?9?
10 class LRUCache{
11 public:
12 ? ? LRUCache(int capacity):_capacity(capacity) {};
13 ? ??
14 ? ? int get(int key);
15 ? ? void set(int key, int value);
16 ? ??
17 private:
18 ? ? std::unordered_map::iterator> keyToNodeItr;
19 ? ? std::list lru;
20 ? ??
21 ? ? int _capacity;
22 };
23?
24 void LRUCache::set(int key, int value) {
25 ? ? auto itr = keyToNodeItr.find(key);
26 ? ? if (itr != keyToNodeItr.end()) { // set value
27 ? ? ? ? itr->second->value = value;
28 ? ? ? ? KeyValue tmp(itr->second->key, itr->second->value);
29 ? ? ? ? keyToNodeItr.erase(itr->second->key);
30 ? ? ? ? lru.erase(itr->second);
31 ? ? ? ? lru.push_front(tmp);
32 ? ? } else { // insert value
33 ? ? ? ? if (lru.size() != _capacity) {
34 ? ? ? ? ? ? lru.push_front(KeyValue(key, value));
35 ? ? ? ? } else {
36 ? ? ? ? ? ? // pop back lru
37 ? ? ? ? ? ? if (lru.size() != 0) {
38 ? ? ? ? ? ? ? ? keyToNodeItr.erase((lru.rbegin())->key);
39 ? ? ? ? ? ? ? ? lru.pop_back();
40 ? ? ? ? ? ? }
41 ? ? ? ? ? ? lru.push_front(KeyValue(key, value));
42 ? ? ? ? }
43 ? ? }
44 ? ??
45 ? ? keyToNodeItr.insert(std::pair::iterator>(key, lru.begin()));
46 }
47?
48 int LRUCache::get(int key) {
49 ? ? auto itr = keyToNodeItr.find(key);
50 ? ? if (itr != keyToNodeItr.end()) {
51 ? ? ? ? int value = itr->second->value;
52 ? ? ? ??
53 ? ? ? ? KeyValue tmp(itr->second->key, itr->second->value);
54 ? ? ? ? keyToNodeItr.erase(itr->second->key);
55 ? ? ? ? lru.erase(itr->second);
56 ? ? ? ? lru.push_front(tmp);
57 ? ? ? ? keyToNodeItr.insert(std::pair::iterator>(key, lru.begin()));
58 ? ? ? ??
59 ? ? ? ? return value;
60 ? ? }
61 ? ? return -1;
62 }
?
因为链表中存储的为cache的实际空间，因此当需要改变cache的位置时，链表及map都需要改变，开销较大。
?
?
?
版本二
使用std::list维护LRU，链表中存储cache的指针。Runtime：186ms。
?
?
?1 #include
?2 #include
?3?
?4 struct KeyValue {
?5 ? ? KeyValue(int pKey, int pValue):key(pKey), value(pValue) {};
?6 ? ? int key;
?7 ? ? int value;
?8 };
?9?
10 class LRUCache{
11 public:
12 ? ? LRUCache(int capacity):_capacity(capacity) {};
13 ? ??
14 ? ? int get(int key);
15 ? ? void set(int key, int value);
16 ? ??
17 ? ? ~LRUCache();
18 ? ??
19 private:
20 ? ? std::unordered_map::iterator> keyToNodeItr;
21 ? ? std::list lru;
22 ? ??
23 ? ? int _capacity;
24 };
25?
26 LRUCache::~LRUCache() {
27 ? ? for (auto itr = lru.begin()