lru-cache.cpp (2230B)
1 class Node { 2 public: 3 Node* next; 4 Node* prior; 5 int value; 6 int key; 7 }; 8 9 class LRUCache { 10 private: 11 Node* head = nullptr; 12 Node* tail = nullptr; 13 int cap = 0; 14 unordered_map<int, Node*> lookup {}; 15 16 public: 17 18 LRUCache(int capacity) { 19 this->cap = capacity; 20 } 21 22 int get(int key) { 23 if(lookup.contains(key)) { 24 Node* current = lookup[key]; 25 26 if(current != tail) { 27 Node* pr = current->prior; 28 if(pr != nullptr) { 29 pr->next = current->next; 30 } else { 31 head = current->next; 32 } 33 current->next->prior = pr; 34 35 current->prior = tail; 36 tail->next = current; 37 tail = current; 38 current->next = nullptr; 39 } 40 return current->value; 41 } 42 return -1; 43 } 44 45 void put(int key, int value) { 46 if(lookup.contains(key)) { 47 Node* cr = lookup[key]; 48 cr->value = value; 49 50 if(cr != tail) { 51 if(cr->prior != nullptr) { 52 cr->prior->next = cr->next; 53 } else { 54 head = cr->next; 55 } 56 cr->next->prior = cr->prior; 57 58 cr->prior = tail; 59 tail->next = cr; 60 tail = cr; 61 cr->next = nullptr; 62 } 63 64 } else { 65 if(lookup.size() >= cap) { 66 lookup.erase(head->key); 67 Node* nHead = head->next; 68 delete head; 69 head = nHead; 70 71 if(head != nullptr) head->prior = nullptr; 72 else tail = nullptr; 73 } 74 75 Node* nextNodePtr = new Node(); 76 nextNodePtr->value = value; 77 nextNodePtr->key = key; 78 lookup[key] = nextNodePtr; 79 80 if(tail != nullptr) { 81 nextNodePtr->prior = tail; 82 tail->next = nextNodePtr; 83 tail = nextNodePtr; 84 } else { 85 tail = nextNodePtr; 86 head = nextNodePtr; 87 } 88 } 89 } 90 };