C++ 实现有序字典（哈希表加双向链表）

来自LeetCode的一道题目，要求在O(1)时间实现带有LRU的Get，Set数据结构。

下面给出实现的方法：

Public需要实现的有，put; get; 构造函数；

Private需要实现的有，size；capacity；head，tail结点；hash表cache；poptail；moveToHead；removeNode；addNode;(通常的双向链表的实现方式)

下面给出代码：

class LRUCache {

public:

    struct LRUNode{

        int key;

        int val;

        LRUNode* pre;

        LRUNode* next;

    };

    LRUCache(int capacity) {

        this->size    = 0;

        this->capacity = capacity;

        head = new LRUNode;

        tail = new LRUNode;

        head->next    = tail;

        tail->pre    = head;

    } 

    int get(int key) {

        if(hash_table.count(key) == 0){

            return -1;

        }

        else{

            auto item = hash_table[key];

            moveToHead(item);

            return item->val;

        }

    }

    void put(int key, int value) {

        if(hash_table.count(key) == 0){

            auto newNode = new LRUNode;

            newNode->key  = key;

            newNode->val  = value;

            hash_table[key] = newNode;

            addNode(newNode);

            size++;

            if(size > capacity){

                popTail();

                size--;

            }

        }

        else{

            hash_table[key]->val = value;

        }

        moveToHead(hash_table[key]);

    }

private:

    int size;

    int capacity;

    LRUNode* head;

    LRUNode* tail;

    unordered_map<int, LRUNode*> hash_table;

    void popTail(){

        auto node = tail->pre;

        tail->pre = this->tail->pre->pre;

        tail->pre->next = tail;

        hash_table.erase(node->key);

        delete node;

    }

    void moveToHead(LRUNode* node){

        removeNode(node);

        addNode(node);

    }

    void removeNode(LRUNode* node){

        node->pre->next = node->next;

        node->next->pre = node->pre;

    }

    void addNode(LRUNode* node){

        node->next    = head->next;

        node->pre      = head;

        head->next    = node;

        node->next->pre = node;

    }

};

/**

* Your LRUCache object will be instantiated and called as such:

* LRUCache* obj = new LRUCache(capacity);

* int param_1 = obj->get(key);

* obj->put(key,value);

*/