5/18/2014

Leetcode -- LRU Cache

class LRUCache{  
 public:  
   list<vector<int> > _list;  
   unordered_map<int, list<vector<int> >::iterator> _hash;  
   int _capacity;  
   LRUCache(int capacity): _capacity(capacity) {  
   }  
   int get(int key) {  
    if(_hash.count(key) > 0) {  
      auto it = _hash[key];  
      vector<int> temp(*it);  
      _list.erase(it);  
      _list.push_front(temp);  
      _hash[key] = _list.begin();  
      return temp[1];  
    } else {  
      return -1;  
    }  
   }  
   void set(int key, int value) {  
     if(_hash.count(key) > 0) {  
       auto it = _hash[key];  
       _list.erase(it);  
       _list.push_front(vector<int>{key, value});  
       _hash[key] = _list.begin();  
     } else {  
       if(_hash.size() >= _capacity) {  
         vector<int> temp(_list.back());  
         _list.pop_back();  
         _hash.erase(temp[0]);  
       }  
       vector<int> newElement{key, value};  
       _list.push_front(newElement);  
       _hash.emplace(key, _list.begin());  
     }  
   }  
 };  

No comments: