X Tutup
// Source : https://oj.leetcode.com/problems/lru-cache/ // Author : Hao Chen // Date : 2014-10-12 /********************************************************************************** * * 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. * **********************************************************************************/ #include #include #include #include using namespace std; // The idea here is quite simple: // 1) A Map to index the key. O(1) key search time-complexity. // 2) A List to sort the cache data by accessed time. // // Considering there are too many insert/delete opreations for the List, // The ouble linked list is the good data structure to performance it. class Node { public: int key; int value; Node *next, *prev; Node(int k, int v) { key=k; value=v; next = prev = NULL; } //Node(int k, int v, Node* n=NULL, Node* p=NULL): key(k), value(v), next(n), prev(p) {} }; // the following double linked list seems a bit commplicated. class DoubleLinkedList { private: Node *pHead, *pTail; int size; public: DoubleLinkedList(){ pHead = pTail = NULL; size = 0; } ~DoubleLinkedList() { while(pHead!=NULL){ Node*p = pHead; pHead = pHead->next; delete p; } } int Size() const { return size; } Node* NewAtBegin(int key, int value) { Node *n = new Node(key, value); return AddAtBegin(n); } Node* NewAtEnd(int key, int value) { Node *n = new Node(key, value); return AddAtEnd(n); } Node* AddAtBegin(Node* n){ size++; if (pHead==NULL) { pHead = pTail = n; return n; } n->next = pHead; n->prev = NULL; pHead->prev = n; pHead = n; return n; } Node* AddAtEnd(Node* n) { size++; if (pHead==NULL) { pHead = pTail = n; return n; } pTail->next = n; n->prev = pTail; n->next = NULL; pTail = n; } void Unlink(Node* n){ Node* before = n->prev; Node* after = n->next; if (before){ before->next = after; } if (after){ after->prev = before; } if(pHead == n){ pHead = pHead->next; }else if(pTail == n) { pTail = pTail->prev; } size--; } void Delete(Node* n){ Unlink(n); delete n; } void TakeToBegin(Node* n){ Unlink(n); AddAtBegin(n); } Node* GetTailNode() { return pTail; } void DeleteLast() { Delete(pTail); } void Print(){ Node* p = pHead; while(p!=NULL) { cout << "(" << p->key << "," << p->value << ") "; p = p->next; } cout << endl; } }; class LRUCache{ private: //cacheList - store the date DoubleLinkedList cacheList; //cacheMap - index the date for searching map cacheMap; //the max capcity of cache int capacity; public: LRUCache(int capacity) { this->capacity = capacity; } void print(){ cacheList.Print(); } int get(int key) { // The accessed node must be up-to-time -- take to the front if (cacheMap.find(key) != cacheMap.end() ){ cacheList.TakeToBegin(cacheMap[key]); return cacheMap[key]->value; } return -1; } void set(int key, int value) { // key found, update the data, and take to the front if (cacheMap.find(key) != cacheMap.end() ){ Node *p = cacheMap[key]; p->value = value; cacheList.TakeToBegin(cacheMap[key]); }else{ // key not found, new a node to store data cacheMap[key] = cacheList.NewAtBegin(key, value); // if the capacity exceed, remove the last one. if( cacheList.Size() > capacity) { int key = cacheList.GetTailNode()->key; cacheMap.erase(key); cacheList.DeleteLast(); } } } }; int main(int argc, char** argv) { /* LRUCache c(2); c.set(2,1); c.print(); c.set(2,2); c.print(); c.get(2); c.print(); c.set(1,1); c.print(); c.set(4,1); c.print(); c.get(2); c.print(); cout << "---------" << endl; */ srand(time(0)); int capacity = 5; int test_loop_times = 10; if (argc>1){ capacity = atoi(argv[1]); } if (argc>2){ test_loop_times = atoi(argv[1]); } LRUCache cache(capacity); int v; for(int i=0; i
X Tutup