Leetcode：LRUCache四個版本實現
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 <list>
2 #include <unordered_map>
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<int, std::list<KeyValue>::iterator> keyToNodeItr;
19 std::list<KeyValue> 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<int, std::list<KeyValue>::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<int, std::list<KeyValue>::iterator>(key, lru.begin()));
58
59 return value;
60 }
61 return -1;
62 }
因為鏈表中存儲的為cache的實際空間，因此當需要改變cache的位置時，鏈表及map都需要改變，開銷較大。
版本二
使用std::list維護LRU，鏈表中存儲cache的指針。Runtime：186ms。
1 #include <list>
2 #include <unordered_map>
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<int, std::list<KeyValue*>::iterator> keyToNodeItr;
21 std::list<KeyValue*> lru;
22
23 int _capacity;
24 };
25
26 LRUCache::~LRUCache() {
27 for (auto itr = lru.begin(); itr != lru.end(); ++itr) {
28 delete *itr;
29 }
30 }
31
32 void LRUCache::set(int key, int value) {
33 auto itr = keyToNodeItr.find(key);
34 if (itr != keyToNodeItr.end()) { // set value
35 KeyValue* tmp = *(itr->second);
36 tmp->value = value;
37 lru.erase(itr->second);
38 lru.push_front(tmp);
39 itr->second = lru.begin(); // avoid invalid iterator
40 } else { // insert value
41 if (lru.size() == _capacity) { // pop back lru
42 KeyValue* tmp = *(lru.rbegin());
43 keyToNodeItr.erase(tmp->key);
44 delete tmp;
45 lru.pop_back();
46 }
47 lru.push_front(new KeyValue(key, value));
48 keyToNodeItr.insert(std::pair<int, std::list<KeyValue*>::iterator>(key, lru.begin()));
49 }
50 }
51
52 int LRUCache::get(int key) {
53 auto itr = keyToNodeItr.find(key);
54 if (itr != keyToNodeItr.end()) {
55 KeyValue* kvPtr = *(itr->second);
56 lru.erase(itr->second);
57 lru.push_front(kvPtr);
58 itr->second = lru.begin();
59 return kvPtr->value;
60 }
61 return -1;
62 }
需要注意的問題是map中存儲的為list的迭代器，因此map中仍需要重新設置key到迭代器的映射，避免迭代器失效。
版本三
似乎std::list太笨重了，so實現輕量級雙鏈表代替std::list。Runtime: 77ms。
1 struct BiListNode {
2 BiListNode() {};
3 BiListNode(int key, int value):key(key), value(value) {};
4 int key;
5 int value;
6 BiListNode* pre;
7 BiListNode* next;
8 };
9
10 class BiList {
11 public:
12 BiList():_count(0) {
13 _head = new BiListNode();
14 _head->pre = _head;
15 _head->next = _head;
16 }
17
18 void push_front(BiListNode* pNode);
19
20 void move_front(BiListNode* pNode);
21
22 BiListNode* begin() {
23 return _head->next;
24 }
25
26 BiListNode* rbegin() {
27 return _head->pre;
28 }
29
30 void pop_back();
31
32 int size() { return _count; }
33
34 ~BiList();
35
36 private:
37 BiListNode* _head;
38 int _count;
39 };
40
41 void BiList::push_front(BiListNode* pNode) {
42 pNode->next = _head->next;
43 pNode->pre = _head;
44 _head->next->pre = pNode;
45 _head->next = pNode;
46 if (_head->pre == _head) {
47 _head->pre = pNode;
48 }
49 ++_count;
50 }
51
52 void BiList::move_front(BiListNode* pNode) {
53 if (pNode == _head->next) {
54 return;
55 }
56 pNode->pre->next = pNode->next;
57 pNode->next->pre = pNode->pre;
58
59 pNode->next = _head->next;
60 pNode->pre = _head;
61
62 _head->next->pre = pNode;
63
64 _head->next = pNode;
65 }
66
67 void BiList::pop_back() {
68 BiListNode* tailPtr = _head->pre;
69 tailPtr->pre->next = _head;
70 _head->pre = tailPtr->pre;
71 delete tailPtr;
72 --_count;
73 }
74
75 BiList::~BiList() {
76 for (BiListNode* itr = _head->next; itr != _head; itr = itr->next) {
77 delete itr;
78 }
79 delete _head;
80 }
81
82
83 class LRUCache {
84 public:
85 LRUCache(int capacity):_capacity(capacity) {};
86
87 int get(int key);
88
89 void set(int key, int value);
90
91 private:
92 int _capacity;
93
94 BiList biList;
95 std::unordered_map<int, BiListNode*> keyToNodePtr;
96 };
97
98 int LRUCache::get(int key) {
99 auto itr = keyToNodePtr.find(key);
100 if (itr != keyToNodePtr.end()) {
101 biList.move_front(itr->second);
102 return itr->second->value;
103 }
104 return -1;
105 }
106
107 void LRUCache::set(int key, int value) {
108 auto itr = keyToNodePtr.find(key);
109 if (itr != keyToNodePtr.end()) { // set value
110 itr->second->value = value;
111 biList.move_front(itr->second);
112 } else { // insert
113 if (biList.size() == _capacity) {
114 keyToNodePtr.erase((biList.rbegin())->key);
115 biList.pop_back();
116 }
117 biList.push_front(new BiListNode(key, value));
118 keyToNodePtr.insert(std::pair<int, BiListNode*>(key, biList.begin()));
119 }
120 }
自己實現的雙鏈表僅有80行代碼，代碼運行效率大大提高。
版本四
雙鏈表都自己實現了，就死磕到底，再自己實現個開鏈哈希表吧。Runtime：66ms。
1 struct BiListNode {
2 BiListNode() {};
3 BiListNode(int key, int value):key(key), value(value) {};
4 int key;
5 int value;
6 BiListNode* pre;
7 BiListNode* next;
8 };
9
10 class BiList {
11 public:
12 BiList():_count(0) {
13 _head = new BiListNode();
14 _head->pre = _head;
15 _head->next = _head;
16 }
17
18 void push_front(BiListNode* pNode);
19
20 void move_front(BiListNode* pNode);
21
22 BiListNode* begin() {
23 return _head->next;
24 }
25
26 BiListNode* rbegin() {
27 return _head->pre;
28 }
29
30 void pop_back();
31
32 int size() { return _count; }
33
34 ~BiList();
35
36 private:
37 BiListNode* _head;
38 int _count;
39 };
40
41 void BiList::push_front(BiListNode* pNode) {
42 pNode->next = _head->next;
43 pNode->pre = _head;
44 _head->next->pre = pNode;
45 _head->next = pNode;
46 if (_head->pre == _head) {
47 _head->pre = pNode;
48 }
49 ++_count;
50 }
51
52 void BiList::move_front(BiListNode* pNode) {
53 if (pNode == _head->next) {
54 return;
55 }
56 pNode->pre->next = pNode->next;
57 pNode->next->pre = pNode->pre;
58
59 pNode->next = _head->next;
60 pNode->pre = _head;
61
62 _head->next->pre = pNode;
63
64 _head->next = pNode;
65 }
66
67 void BiList::pop_back() {
68 BiListNode* tailPtr = _head->pre;
69 tailPtr->pre->next = _head;
70 _head->pre = tailPtr->pre;
71 delete tailPtr;
72 --_count;
73 }
74
75 BiList::~BiList() {
76 for (BiListNode* itr = _head->next; itr != _head; itr = itr->next) {
77 delete itr;
78 }
79 delete _head;
80 }
81
82 struct hashNode {
83 hashNode(int key, BiListNode* ptr):key(key), ptr(ptr), next(NULL) {};
84 int key;
85 BiListNode* ptr;
86 hashNode* next;
87 };
88
89 class HashTable {
90 public:
91 HashTable(int capacity);
92
93 hashNode* find(int key);
94
95 void insert(int key, BiListNode* ptr);
96
97 void erase(int key);
98
99 ~HashTable();
100
101 private:
102 int _capacity;
103 hashNode** hashArray;
104 };
105
106 HashTable::HashTable(int capacity):_capacity(capacity) {
107 hashArray = new hashNode*[capacity];
108 for (int i = 0; i < _capacity; ++i) {
109 hashArray[i] = NULL;
110 }
111 }
112
113 hashNode* HashTable::find(int key) {
114 for (hashNode* itr = hashArray[key % _capacity]; itr != NULL;
115 itr = itr->next) {
116 if (itr->key == key) {
117 return itr;
118 }
119 }
120 return NULL;
121 }
122
123 void HashTable::insert(int key, BiListNode* ptr) {
124 hashNode* tmp = new hashNode(key, ptr);
125
126 int relativeKey = key % _capacity;
127
128 if (hashArray[relativeKey] == NULL) {
129 hashArray[relativeKey] = tmp;
130 return;
131 }
132
133 tmp->next = hashArray[relativeKey];
134 hashArray[relativeKey] = tmp;
135 }
136
137 void HashTable::erase(int key) {
138 for (hashNode* pre = hashArray[key % _capacity], *itr = pre;
139 itr != NULL; pre = itr, itr = itr->next) {
140 if (itr->key == key) {
141 if (itr != pre)
142 pre->next = itr->next;
143 else // head
144 hashArray[key % _capacity] = itr->next;
145
146 delete itr;
147 }
148 }
149 }
150
151 HashTable::~HashTable() {
152 for (int i = 0; i < _capacity; ++i) {
153 for (hashNode* itr = hashArray[i]; itr != NULL;) {
154 hashNode* tmp = itr;
155 itr = itr->next;
156 delete tmp;
157 }
158 }
159 delete [] hashArray;
160 }
161
162 class LRUCache {
163 public:
164 LRUCache(int capacity):_capacity(capacity) {
165 hashTable = new HashTable(1024);
166 };
167
168 int get(int key);
169
170 void set(int key, int value);
171
172 ~LRUCache() { delete hashTable; }
173
174 private:
175 int _capacity;
176 BiList bilist;
177 HashTable* hashTable;
178 };
179
180 int LRUCache::get(int key) {
181 hashNode* tmp = hashTable->find(key);
182 if (tmp != NULL) {
183 bilist.move_front(tmp->ptr);
184 return tmp->ptr->value;
185 }
186 return -1;
187 }
188
189 void LRUCache::set(int key, int value) {
190 hashNode* tmp = hashTable->find(key);
191 if (tmp != NULL) { // set
192 bilist.move_front(tmp->ptr);
193 tmp->ptr->value = value;
194 return;
195 }
196
197 // insert
198 if (bilist.size() == _capacity) {
199 hashTable->erase((bilist.rbegin())->key);
200 bilist.pop_back();
201 }
202
203 bilist.push_front(new BiListNode(key, value));
204 hashTable->insert(key, bilist.begin());
205 }
