for Robot Artificial Inteligence

67. LRU Cache

21 Aug 2020 | Daily Algorithms

  • There is a similar example in Java, but I wanted to share my solution using the new C++11 unordered_map and a list. The good thing about lists is that iterators are never invalidated by modifiers (unless erasing the element itself). This way, we can store the iterator to the corresponding LRU queue in the values of the hash map. Since using erase on a list with an iterator takes constant time, all operations of the LRU cache run in constant time.

class LRUCache {
public:
    LRUCache(int capacity) {
        size = capacity;
    } // LRUCache(int capacity) : size(capacity);

    int get(int key) {
        if(kv.count(key)==0)
            return -1;
        updateLRU(key);
        return kv[key];
    }

    void put(int key, int value) {
        if(kv.size() == size && kv.count(key) == 0)
        {
            evict();
        }
        updateLRU(key);
        kv[key] = value;

    }
    void updateLRU(int key)
    {
        if(kv.count(key))
        {
            LRU.erase(mp[key]);
        }
        LRU.push_front(key);
        mp[key] = LRU.begin();
    }
    void evict(){
        mp.erase(LRU.back());
        kv.erase(LRU.back());
        LRU.pop_back();
    }
private:
    int size;
    list<int> LRU; // MRU..LRU
    unordered_map<int, list<int>::iterator> mp; //key-> iterator
    unordered_map<int, int> kv; // key->value


};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

Comments