C++ O(1) using DoubleLinkedList and 2 unordered_map


  • 0

    A list node stores key, value and frequency. One map is used to link key with its node, and the other map is used to link a frequency with the node that is closest to the tail and contains that frequency. Every operation maintains the order: from head to tail, lowest frequency to highest frequency and for the same frequency, least recently to most recently

    class CaNode{
    public:
        int key, val, freq;
        CaNode *next, *prev;
        CaNode(int k, int v): key(k), val(v) {
            freq = 1;
            next = nullptr;
            prev = nullptr;
        }
    };
    
    class LFUCache {
    public:
        LFUCache(int capacity) {
            max = capacity;
            size = 0;
            head = new CaNode(-1, -1);
            last[1] = head;
        }
        
        int get(int key) {
            if(max == 0) return -1;
            CaNode* node = keyToNode[key];
            if(node) {
                update(node);
                return node->val;
            }else{
                return -1;
            }
        }
        
        void set(int key, int value) {
            if(max == 0) return;
            CaNode* node = keyToNode[key];
            if(node){
                update(node);
                node->val = value;   
            }else{
                if(size == max)
                    del(head->next);
                else
                    size++;
                insert(key, value);
            }
        }
        
        void update(CaNode* node){
            int freq = ++ node->freq;
            CaNode *temp = last[freq-1];
            if(last[freq-1] == node){
                if(node->prev->freq == freq-1){
                    last[freq-1] = node->prev;
                }else{
                    last[freq-1] = nullptr;
                }
            }
            
            if(last[freq])
                move(node, last[freq]);
            else if(temp != node)
                move(node, last[freq-1]);
            
            last[freq] = node;
        }
        
        void move(CaNode *node, CaNode *pos){
            node->prev->next = node->next;
            node->next->prev = node->prev;
            node->next = pos->next;
            node->prev = pos;
            if(pos->next) pos->next->prev = node;
            pos->next = node;
        }
        
        void del(CaNode *node){
            node->prev->next = node->next;
            if(node->next) node->next->prev = node->prev;
            keyToNode.erase(node->key);
            if(last[node->freq] == node){
                if(node->prev->freq == node->freq){
                    last[node->freq] = node->prev;
                }else{
                    last[node->freq] = nullptr;
                }
            }
            delete node;
        }
        
        void insert(int key, int value){
            CaNode *newNode = new CaNode(key, value);
            CaNode *pos = last[1];
            newNode->next = pos->next;
            newNode->prev = pos;
            if(pos->next) pos->next->prev = newNode;
            pos->next = newNode;
            last[1] = newNode;
            keyToNode[key] = newNode;
        }
        
    private:
        int max, size;
        unordered_map<int, CaNode*> keyToNode;
        unordered_map<int, CaNode*> last;
        CaNode *head;
    };
    

Log in to reply
 

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