LRU-cache(map+list).cpp

struct node{
    int key;
    int value;
    node* prev;
    node* next;
    node(int _key, int _value) {
        key = _key;
        value = _value;
        prev = NULL;
        next = NULL;
    }
};

class LRUCache{
private:
    int _capacity;
    int _len;

    node* head;
    node* tail;

    map<int, node*> mp;

    /*
    void insertToHead(node* cur) {
        cur->next = head->next;
        cur->prev = head;

        cur->next->prev = cur;
        head->next = cur;
    }
    */

    void insertToHead(node* cur) {
        node* p = head->next;

        cur->next = p;
        cur->prev = head;

        head->next = cur;
        p->prev = cur;
    }

    void deleteNode(node* cur) {

    }

public:
    LRUCache(int capacity) {
        _capacity = capacity;
        _len = 0;

        head = new node(-1, -1);
        tail = new node(-1, -1);

        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        map<int, node*>::iterator it = mp.find(key);

        if(it != mp.end()) {
            node* cur = (*it).second;

            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;

            insertToHead(cur);

            cout << cur->key << " " << cur->value << endl;

            return cur->value;
        }else{
            cout << key << " " << -1 << endl;
            return -1;
        }
    }

    void set(int key, int value) {
        map<int, node*>::iterator it = mp.find(key);

        if (it != mp.end()) {
            node* cur = (*it).second;
            cur->value = value;

            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;

            mp[key] = cur;

            insertToHead(cur);

        }else{
            node* newnode = new node(key, value);
            insertToHead(newnode);
            mp[key] = newnode;


            if (_len < _capacity) {
                _len ++;
            }else{
                node *cur = tail->prev;
                tail->prev = cur->prev;
                cur->prev->next = tail;

                map<int, node*>::iterator subit = mp.find(cur->key);

                mp.erase(subit);

                delete cur;
            }
        }
    }
};