80ms C++ unordered_map and doubly-linked list


  • 0
    H

    I used a list to store key and val.
    lastly used element is put to the front (head), using touchit() function.
    For retrieval I used unordered_list

    struct DListNode{
        int val;
        int key;
        DListNode *prev=NULL;
        DListNode *next=NULL;
        DListNode(int x,int k):val(x),key(k){};
    };
    
    
    
    class LRUCache{
    
        unordered_map<int,DListNode*> mp;
        DListNode* head=NULL, *end=NULL;
        int cap;
        
        void touchit(DListNode *p)
        {
            if (p == head)
                return;
            else
            {
                p->prev->next = p->next;
            }
            if (p->next)
                p->next->prev = p->prev;
            else
            end = p->prev;
    
            head -> prev = p; 
            p -> next = head;
            head = p; p->prev = NULL;
    
        }
    
    public:
    
        LRUCache(int capacity) {
            cap = capacity;
        }
    
        int get(int key) {
            if (mp.find(key)!= mp.end())
            {
                touchit(mp[key]);
                return mp[key]->val;
            }
            else
                return -1;
        }
    
        void set(int key, int value) {
            if ( mp.find(key)!= mp.end() )
            {
                touchit(mp[key]);
                mp[key] -> val = value;
            }
            else 
            {   
                if (mp.size()==cap)
                {
                    mp.erase(end->key);
                    DListNode *t = end -> prev;
                    delete end;
                    end = t;
                    if (t) 
                    {
                        t -> next = NULL;
                    }
    
                }
    
                DListNode *t = new DListNode(value,key);
                if (t!=head) t -> next = head;
                if (head == NULL || head == t ) 
                    end = t;
                else
                    head ->prev = t;
    
                head = t;
                mp[key] = t;
            }
        }
    
    };

Log in to reply
 

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