[LeetCode] LRU Cache

Link : LRU Cache

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.

Analysis :
To get a value with specified key is not a problem, but to get the oldest(or least recently used) item is a challenge, we have several choices though.
a) need a queue, and the oldest is just at the front
b) data structure like array, key a variable to record the last use, every time we need to get the oldest item, the whole data structure is traversed
c) a heap that could pop the oldest item.

Insert and Delete
b) is easy to implement but delete is time consuming.
c) is quite good but hard to implement.
a) if with a double linked list, insert and delete is O(1) time complexity.

Record The Last Use
a) is naturally sort the data in FIFO order so oldest is at the front
b) either simulate queue operation, or keep a variable to record the use
c) heap could be generated using the last time use as the key

Access
map is the first choice. And combine map with other data structure, we can easily complete access, insert and delete operation.


Personally, I like this implementation(using STL list, and the map stores list iterator. The result is just amazing).
Please enjoy it at http://www.cnblogs.com/TenosDoIt/p/3417157.html

My implementation is as below.

 #include < iostream >  
 #include < unordered_map >  
 class LRUCache {  
   public: struct DoubleLinkedList {  
     int key;  
     int value;  
     DoubleLinkedList * pre;  
     DoubleLinkedList * next;  
     DoubleLinkedList(int _key, int _value): key(_key),  
     value(_value) {}  
   };  
   LRUCache(int capacity): max(capacity),  
   count(0) {  
     head = new DoubleLinkedList(0, -1);  
     tail = new DoubleLinkedList(0, -2);  
     head - > next = tail;  
     tail - > pre = head;  
   }  
   int get(int key) {  
     if ((map.find(key) == map.end()) || map[key] == NULL) // if we use map.erase, NULL comparision is not necessary  
       return -1;  
     refresh(key);  
     return map[key] - > value;  
   }  
   void set(int key, int value) {  
     DoubleLinkedList * entry;  
     if ((map.find(key) == map.end()) || map[key] == NULL) // if we use map.erase, NULL comparision is not necessary  
     {  
       if (count == max)  
         deleteOldest();  
       entry = new DoubleLinkedList(key, value);  
       map[key] = entry;  
       insert(entry);  
     } else {  
       map[key] - > value = value;  
       refresh(key);  
     }  
   }  
   void insert(DoubleLinkedList * entry) {  
     // be much much more careful !!!!!  
     entry - > next = head - > next;  
     entry - > pre = head;  
     head - > next - > pre = entry;  
     head - > next = entry;  
     count++;  
   }  
   void deleteOldest() {  
     DoubleLinkedList * pre = tail - > pre;  
     DoubleLinkedList * prepre = tail - > pre - > pre;  
     // list change  
     prepre - > next = tail;  
     tail - > pre = prepre;  
     // map change  
     map[pre - > key] = NULL; // if use map.erase[key], the item is removed from map, and also destroyed  
     // memory change  
     delete pre;  
     // count change  
     count--;  
   }  
   void refresh(int key) {  
     DoubleLinkedList * entry = map[key];  
     entry - > pre - > next = entry - > next;  
     entry - > next - > pre = entry - > pre;  
     count--;  
     insert(entry);  
   }  
   private: int max;  
   int count;  
   DoubleLinkedList * head;   
   DoubleLinkedList * tail;   
   // we can use the STL list for quick implementation  
   // STL list support insert, pop, splice(powerful)  
   // and with STL list, we don't have to care about the memory management  
   // DoubleLinkedList node is copied into the list object  
   // bad side is the time to copy might be slightly more.  
   std::unordered_map < int, DoubleLinkedList * > map;  
 };