C++ LRU缓存

题���：

//构建双向链表的节点结构（要有两个构造函数）struct Node{    int key, val;    Node* pre;    Node* next;    Node():key(0), val(0), pre(nullptr), next(nullptr) {}    Node(int _key, int _val): key(_key), val(_val), pre(nullptr), next(nullptr) {}};class LRUCache {private:    //哈希表存放key和节点的映射    unordered_map m;    Node* head;    Node* tail;    int capacity, size;public:    //LRU构造函数中，设定capacity和size（当前容量）、创建伪头、尾节点并相连    LRUCache(int _capacity) : capacity(_capacity), size(0){        head = new Node();        tail = new Node();        head->next = tail;        tail->pre = head;    }        //取值：如果表里没有这个key，返回-1；如果有，更新节点值，并将其移动至头部    int get(int key) {        if(!m.count(key)) return -1;        Node* node = m[key];        remove(node);        add(node);        return node->val;    }        //放值：如果表里找到，更新值并移动到头部；如果没找到，执行插入操作，插入前先判断是否溢出容量，是的话移除尾部节点，还要将其从表里删除，当前容量减一，然后将新节点加入头部、表、容量加一    void put(int key, int value) {        if(m.count(key)){            Node* node = m[key];            node->val = value;            remove(node);            add(node);        }else{            Node* node = new Node(key, value);            if(size==capacity){                Node* del = tail->pre;                m.erase(del->key);                remove(del);                size--;            }            add(node);            size++;            m[key] = node;        }    }        //删除节点    void remove(Node* node){        node->pre->next = node->next;        node->next->pre = node->pre;    }        //将节点移动至头结点    void add(Node* node){        node->next = head->next;        node->pre = head;                head->next->pre = node;        head->next = node;    }};

参考视频：LeetCode 每日一题146. LRU 缓存 | 手写图解版思路 + 代码讲解