LRU Cache

来源：Leetcode, Facebook Onsite

原帖：http://oj.leetcode.com/problems/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.

思考：
Hashmap + linkedlist. 03/12/2015 FB的onsite的时候遇到了这道题，题目发生了变化，但本质就是LRU。主要要考虑get和set的时候lru的性质。

代码：

 class LRUCache{  
 public:  
     LRUCache(int capacity) {  
         size = capacity;    
     }  
   
     int get(int key) {  
         if(!kmap.count(key)) return -1;  
         cachelist.splice(cachelist.begin(), cachelist, kmap[key]);  
         return kmap[key]->value;  
     }  
   
     void set(int key, int value) {  
         if(kmap.count(key)){  
             cachelist.splice(cachelist.begin(), cachelist, kmap[key]);  
             kmap[key]->value = value;  
         } else {  
             if(cachelist.size() == size){  
                 kmap.erase(cachelist.back().key);  
                 cachelist.pop_back();  
             }  
             cachelist.push_front(data(key, value));  
             kmap[key] = cachelist.begin();  
         }  
     }  
 private:  
     struct data{  
         int key;  
         int value;  
         data(int k, int v) : key(k), value(v) {}  
     };  
   
     int size;  
     list<data> cachelist;  
     unordered_map<int, list<data>::iterator> kmap;  
 };