LRU缓存C++

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1，并将1节点放到最上方
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

class Node{
public:
    int key;
    int value;
    // 双链表，节约查找时间
    Node* pre;
    Node* next;

    Node(int k=0, int v=0):key(k), value(v){}
};

class LRUCache {
private:
    int capacity;  
    Node* dummy;     // 哨兵节点
    unordered_map<int, Node*> key_to_node;    // 建立key到节点的映射
    // 删除一个节点(双链表的删除操作)
    void remove(Node* x){
        x->pre->next = x->next;
        x->next->pre = x->pre;
    }
    // 在链表头添加一个节点(双链表的添加操作)
    void push_front(Node* x){
        x->pre=dummy;
        x->next = dummy->next;
        x->pre->next = x;
        x->next->pre = x;
    }
    // 获取key对应节点，把该节点移到链表头部
    Node* get_node(int key){
        auto it = key_to_node.find(key);
        if(it == key_to_node.end())  // 没找到
        {
            return nullptr;
        }
        Node* node = it->second;
        remove(node);   // 在原位置删掉
        push_front(node);   // 在新位置添加
        return node;
    }
public:
    LRUCache(int capacity):capacity(capacity), dummy(new Node()) {
        // 初始化双链表
        dummy->pre = dummy;
        dummy->next = dummy;
    }
    
    int get(int key) {
        Node* node = get_node(key);
        // 没找到返回-1
        return node?node->value:-1;
    }
    
    void put(int key, int value) {
        Node* node=get_node(key);
        // 先找是否在链表中，若在链表中则更新value的值
        if(node){
            node->value = value;
            return;
        }
        // 若不在链表中，则创建一个新的节点，插入
        node = new Node(key, value);
        key_to_node[key] = node;
        push_front(node);
        // 若插入后大于了总容量，则删掉一个结点
        if(key_to_node.size() > capacity){
            Node* back_node = dummy->pre;
            key_to_node.erase(back_node->key);
            remove(back_node);
            delete back_node;
        }
    }
};