Simple C++ Solution


  • 0
    G
    class LRUCache{
        int _capacity;
        list<pair<int, int> > list_of_kv;       // list of key-value pairs
        unordered_map<int, list<pair<int, int> >::iterator> map_of_k;   // map of key->iterator in the list of key-value pairs
    public:
        LRUCache(int capacity) : _capacity(capacity) { }
        
        int get(int key) {
            unordered_map<int, list<pair<int, int> >::iterator>::iterator it = map_of_k.find(key);
            if (it != map_of_k.end()) {                 // key is present
                int val = (*it->second).second;
                list_of_kv.erase(it->second);           // remove and
                list_of_kv.emplace_front(key, val);     // reinsert the element in the front of the list
                map_of_k[key] = list_of_kv.begin();     // update the iterator info in the map
                return val;
            }
            return -1;
        }
        
        void set(int key, int value) {
            unordered_map<int, list<pair<int, int> >::iterator>::iterator it = map_of_k.find(key);
            // if capacity is hit and got a totally new key make space for the new key
            // by freeing up the lru element at the tail of the list
            if (it == map_of_k.end() && map_of_k.size() == _capacity) {
                int key = list_of_kv.back().first;
                list_of_kv.pop_back();
                map_of_k.erase(map_of_k.find(key));
            }
            // if an exisiting key is being updated remove the element from the list,
            // we will insert it again later at the head of the list
            if (it != map_of_k.end()) {
                list_of_kv.erase(it->second);
            }
            list_of_kv.emplace_front(key, value);
            map_of_k[key] = list_of_kv.begin();
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.