LRU Cache; Get RunTime Error. C++


  • 0
    O

    What's wrong with my code?
    Last executed input: 1,[set(2,1),get(1)]

    struct Node{
        int val;
        Node *prev;
        Node *next;
    };
    class LRUCache{
    private:
        Node *head, *tail;
        Node *entries;
        map<int,Node* > key_map;
        vector<Node* > free_entries; 
    public:
        LRUCache(int capacity) {
            entries = new Node[capacity];
            for(int i=0; i<capacity-1; i++)
                free_entries.push_back(entries+i);
            head = new Node();
            tail = new Node();
            head->next = tail;
            head->prev = NULL;
            tail->prev = head;
            tail->next = NULL;
        }
        ~LRUCache(){
            delete head;
            delete tail;
            delete[] entries;
        }
        int get(int key) {
            Node* node = NULL;
            map<int, Node* >::iterator it = key_map.find(key);
            if(it!=key_map.end()){
                node = it->second;
                detach(node);
                attach(node);
                return node->val;
            }
            else 
                return -1;
        }
        void set(int key, int value) {
            Node* node = NULL;
            map<int, Node* >::iterator it = key_map.find(key);
            if(it!=key_map.end()){
                node = it->second;
                detach(node);
                node->val = value;
                attach(node);
            }
            else{
                if(free_entries.empty()){
                    node = tail->prev;
                    detach(node);
                    key_map.erase(key);
                }
                else{
                    node = free_entries.back();
                    free_entries.pop_back();
                }
                node->val = value;
                attach(node);
                key_map[key]=node;
            }
        }
    private:
        void detach(Node *node){
            node->prev->next = node->next;
            node->next->prev = node->prev;
        }
        void attach(Node *node){
            node->prev = head;
            node->next = head->next;
            head->next = node;
            node->next->prev = node;
        }
    };

Log in to reply
 

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