; 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::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, in