学步园

题目：

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the
key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already
present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

解题：

我以为get不会更新的，结果get也会更新，唉。
思路就是用链表搞，设头尾指针，插入时有两种情况：
（1）插入的元素不存在队列中
    1）如果未达到capacity则直接头插法插入
    2）若达到capacity则头插法插入，删除队尾元素
（2）插入的元素存在队列中
    更新一下放到头
查询时等同于插入的元素存在队列中的情况
使用了map将key值映射到一个class中，该class包含value值和队列元素的指针
队列元素包含前后指针和key值

class LRUCache{
public:
    LRUCache(int capacity) {
        this->cap = capacity;
        head = new Node(0);
        tail = new Node(0);
        head->next = tail;
        tail->pre = head;
        mp.clear();
    }

    int get(int key) { //get will update the queue and put the element in front of head
        if(mp.find(key) == mp.end()) return -1;
        Node *now = mp[key]->node;
        Node *preNow = now->pre;
        Node *nxtNow = now->next;
        if(preNow == head) return mp[key]->val;
        preNow->next = nxtNow;
        nxtNow->pre = preNow;
        now->next = head->next;
        head->next->pre = now;
        head->next = now;
        now->pre = head;

        return mp[key]->val;
    }

    void set(int key, int value) {
        if(mp.find(key) == mp.end() || mp[key]->val == -1) { //first used key or doesn't exist in the queue
            Node *now = new Node(key);
            if(cap) { //doesn't reached its capacity
                cap --;
                Node *nxt = head->next;
                now->next = nxt;
                nxt->pre = now;
                head->next = now;
                now->pre = head;
            }
            else {
                //insert in the head
                head->next->pre = now;
                now->next = head->next;
                now->pre = head;
                head->next = now;

                //delete the tail
                Node *pre = tail->pre;
                Node *prepre = pre->pre;
                prepre->next = tail;
                tail->pre = prepre;
                //mp[pre->key]->val = -1; //mark doesn't exist in the queue
                mp.erase(pre->key);
                free(pre);
            }
            Two *two = new Two(value, now);
            //mp[key] = two;
            mp.insert(pair<int, Two *>(key, two));
        }
        else { //exist in the queue
            Node *now = mp[key]->node;
            mp[key]->val = value;
            Node *preNow = now->pre;
            Node *nxtNow = now->next;
            if(preNow == head) return ;
            preNow->next = nxtNow;
            nxtNow->pre = preNow;
            now->next = head->next;
            head->next->pre = now;
            head->next = now;
            now->pre = head;
        }
    }
private:
    class Node {
    public:
        Node *pre, *next;
        int key;
        Node(int x) {
            pre = NULL, next = NULL;
            key = x;
        }
    };
    class Two {
    public:
        int val;
        Node *node;
        Two(int val, Node *node) {
            this->val = val;
            this->node = node;
        }
    };
    map<int, Two *> mp;
    int cap;
    Node *head, *tail;
};