O(1) multimap+unordered_map solution


  • 0
    C

    This is an implementation of the O(1) algorithm introduced in http://www.deepakvadgama.com/blog/lfu-cache-in-O(1)/.
    Use the frequency as the multimap's key and {key,value} as the multimap's value. The insertion order is preserved in the multimap, so the first entry in the multimap is always the least frequently used and least used entry.
    To facilitate O(1) deletion, we need an unordered_map to help locate the entry in the multimap by its key value. If the size limit is reached, we delete first and then insert. Doing it backwards will result in the deletion of the newly added entry.
    Since both get() and put() is regarded as one visit, we update the frequency in get() and invoke get() in put().When updating the frequency, just move(i.e. delete and insert) the entry to key+1 level in the multimap.

    class LFUCache{
        multimap<int,pair<int,int>> dict;
        unordered_map<int,multimap<int,pair<int,int>>::iterator> table;
        int size_limit;
    public:
        // @param capacity, an integer
        LFUCache(int capacity) {
            // Write your code here
            size_limit = capacity;
        }
    
        // @param key, an integer
        // @param value, an integer
        // @return nothing
        void put(int key, int value) {
            // Write your code here
            if( size_limit==0 ) return;
            if( get(key)==-1 ){
                if( table.size()>=size_limit ){
                    int k = (dict.begin()->second).first;
                    dict.erase(dict.begin());
                    table.erase(k);
                }
                multimap<int,pair<int,int>>::iterator it = dict.insert({1,{key,value}});
                table[key] = it;
            }
            else table[key]->second = {key,value};
        }
        
        // @return an integer
        int get(int key) {
            // Write your code here
            if(table.count(key)>0){
                multimap<int,pair<int,int>>::iterator it = dict.insert({table[key]->first+1,table[key]->second});
                dict.erase(table[key]);
                table[key] = it;
                return (table[key]->second).second;
            }
            else return -1;
        }
    };
    

Log in to reply
 

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