hash + 双链表

struct Node{
    int key;
    Node *prev, *nxt;
    Node(int k)
    :key(k),
    prev(nullptr),
    nxt(nullptr)
    {}
};

class LRUCache {
public:
    LRUCache(int capacity) 
    :c(capacity),
    tot(0),
    head(new Node(-1)),
    tail(new Node(-1))
    {
         head->nxt = tail;
         tail->prev = head;
    }

    int get(int key) {
        if(dic.find(key) != dic.end())
        {
            Node* node = dic[key].second;
            // 拿出node转换位置
            setChange(node);

            // 把node插入尾部
            setTail(node);
            return dic[key].first;
        }
        return -1;
    }

    void put(int key, int value) {
        if(dic.find(key) != dic.end())
        {
            Node* node = dic[key].second;

            setChange(node);

            setTail(node);            
            // 改变value值
            dic[key].first = value;
        }
        else{
            if(tot == c)
            {
                setRemove();                
                tot --;
            }
            // 添加value值
            Node* node = new Node(key);
            dic[key] = make_pair(value, node);

            // 插入尾部
            setTail(node);
            tot ++;
        }
    }
private:
    int c, tot;
    Node *head, *tail;
    unordered_map<int, pair<int, Node*>> dic;

    inline void setTail(Node * node)
    {
        // 把node插入尾部
        node->nxt = tail;
        node->prev = tail->prev;

        tail->prev->nxt = node;
        tail->prev = node;
    }

    inline void setChange(Node* node)
    {
        node->prev->nxt = node->nxt;
        node->nxt->prev = node->prev;
    }

    inline void setRemove()
    {
        Node* node = head->nxt;
        dic.erase(node->key);

        // 移除节点
        head->nxt = node->nxt;
        head->nxt->prev = head;
        delete node;
    }
};