设计LRU缓存数据结构

#include <unordered_map>
struct DListNode{
    int key, val;
    DListNode* pre;
    DListNode* next;
    DListNode(int k, int v): key(k), val(v), pre(nullptr), next(nullptr){};
};

class Solution {
private:
    // 当前可用缓存的大小
    int size = 0;
    DListNode* head;
    DListNode* tail;
    unordered_map<int, DListNode*> map;

public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    void set(int key, int val){
        if(map.find(key) == map.end()){ // hashmap 中没找到
            DListNode* node = new DListNode(key, val);
            map[key] = node;
            if(this -> size <= 0){
                removeLast();
            }
            else{
                this -> size --;
            }
            insertFirst(node);
        }
        else{  // hashmap 中已经有了，也就是链表里也已经有了
            map[key] -> val = val;
            moveToHead(map[key]);
        }
    }

    int get(int key){
        int ret = -1;
        if(map.find(key) != map.end()){
            ret = map[key] -> val;
            moveToHead(map[key]);
        }
        return ret;
    }

    void removeLast(){
        map.erase(this -> tail -> pre -> key);
        this -> tail -> pre -> pre -> next = this -> tail;
        this -> tail -> pre = this -> tail -> pre -> pre;
    }

    void moveToHead(DListNode* node){
        if(node -> pre == this -> head) return;
        node -> pre -> next = node -> next;
        node -> next -> pre = node -> pre;
        insertFirst(node);
    }

    void insertFirst(DListNode* node){
        node -> pre = this -> head;
        node -> next = this -> head -> next;
        this -> head -> next -> pre = node;
        this -> head -> next = node;
    }

    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        // 初始化表
        if(k < 1) return {};
        this -> size = k;
        this -> head = new DListNode(0,0);
        this -> tail = new DListNode(0,0);
        this -> head -> next = this -> tail;
        this -> tail -> pre = this -> head;

        // 没有操作
        if(operators.size() == 0) return {};

        vector<int> res;
        for(vector<int> op : operators){
            if(op[0] == 1) {
                set(op[1], op[2]);
            }
            else if(op[0] == 2){
                int value = get(op[1]);
                res.push_back(value);
            }
        }
        return res;
    }
};