Easy Clean Self Explainable C++ code


  • 1
    R

    Basically we have two map,
    1st: key->{value,frequency, pointer to list}
    2nd : frequency-> list of keys with same frequency
    the list holds records the order so the list back front is most recently used key

    class LFUCache {
    public:
        LFUCache(int capacity) {
            maxsize=capacity;
            cursize=0;
            minfreq=0;
        }
        int get(int key) {
            if(hashmap.find(key)==hashmap.end()) return -1;
            Touch(key);
            return hashmap[key].val;
        }
        void put(int key, int value) {
            if(maxsize<=0) return;
            if(get(key) !=-1){
                hashmap[key].val=value;
                return;
            }
            createNewBucket(key, value);
            if(maxsize==cursize){
                cursize--;
                int rm_key = freqmap[minfreq].back();
                freqmap[minfreq].pop_back();
                hashmap.erase(rm_key);
            }
            cursize++;
            minfreq=1;
            return;
        }
        
        void Touch(int key){
            int oldfreq = hashmap[key].freq;
            int newfreq = oldfreq + 1;
            if(oldfreq==minfreq and freqmap[oldfreq].size()==1) minfreq=newfreq;
            
            freqmap[oldfreq].erase(hashmap[key].ptr);
            freqmap[newfreq].push_front(key);
            
            hashmap[key].freq=newfreq;
            hashmap[key].ptr = freqmap[newfreq].begin();
        }
        void createNewBucket(int key, int value){
            Bucket newbucket;
            newbucket.freq = 1;
            newbucket.val = value;
            freqmap[1].push_front(key);
            newbucket.ptr = freqmap[1].begin();
            hashmap[key] = newbucket;
        }
        
        int maxsize;
        int cursize;
        int minfreq;
        struct Bucket{
          int val;
          int freq;
          list<int>::iterator ptr;
        };
        unordered_map<int,Bucket>    hashmap; //key->bucket
        unordered_map<int,list<int>> freqmap; //freq->same freq list list front new
    };
    

Log in to reply
 

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