t value);
?90 ? ??
?91 private:
?92 ? ? int _capacity;
?93 ? ??
?94 ? ? BiList biList;
?95 ? ? std::unordered_map 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(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);