vivek_ragi

LRU_CACHE

Jun 21st, 2021
798
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class LRUCache {
  2. public:
  3.     list<pair<int,int>> cache;
  4.    
  5.     unordered_map <int, list<pair<int,int>>:: iterator> mp; //key -- index in the cache
  6.    
  7.     int size;
  8.    
  9.     void refreshPosition(int key, int value) {
  10.         cache.erase(mp[key]); //remove old position
  11.         cache.push_front({key,value}); //push it in the fornt
  12.         mp[key] = cache.begin(); // assign it to begin
  13.     }
  14.    
  15.     LRUCache(int capacity) {
  16.        this -> size = capacity;
  17.     }
  18.    
  19.     int get(int key) {
  20.         if(mp.find(key) != mp.end()) {
  21.             refreshPosition(key, (*mp[key]).second);
  22.             return (*mp[key]).second;
  23.            
  24.         }
  25.         else {
  26.             return -1;
  27.         }
  28.     }
  29.    
  30.     void put(int key, int value) {
  31.         if(mp.find(key) != mp.end()) {
  32.             refreshPosition(key, value);
  33.         }
  34.         else {
  35.             cache.push_front(make_pair(key,value));
  36.             mp[key] = cache.begin();
  37.            
  38.             if(mp.size() > size) {
  39.                 mp.erase(cache.back().first);
  40.                 cache.pop_back();  
  41.             }
  42.         }
  43.     }
  44. };
  45.  
  46. /**
  47.  * Your LRUCache object will be instantiated and called as such:
  48.  * LRUCache* obj = new LRUCache(capacity);
  49.  * int param_1 = obj->get(key);
  50.  * obj->put(key,value);
  51.  */
RAW Paste Data