LRU缓存实现

一. LRU缓存实现

使用双向链表保证O（1）的优先度更改，同时当做优先队列维护插入顺序
同时这里要结合哈希表，保证更改想要的节点

/*
定义Node 双向链表节点
定义 remove 进行删除节点（只删除节点在链表中的关系）
定义 update 更新指定节点的优先度
定义 insert 插入新的节点
*/


class LRUCache {
public:
    typedef struct Node {//双向链表
        int key;//在哈希中的键值，用于删除哈希
        int data;
        Node* pre;
        Node* next;
        Node() :  key(0), data(0), pre(nullptr), next(nullptr) {}
        Node(int key,int val) :key(key), data(val), pre(nullptr), next(nullptr) {}
    }Node,*pNode;

    int capacity;
    unordered_map<int,pNode> m;
    Node* listpre = new Node();
    Node* listtail = new Node();

    void remove(Node* cur){
        //更改节点关系
        Node* pre = cur->pre;
        Node* next = cur->next;
        pre->next = next;
        next->pre = pre;
    }
    void update(Node* cur){ //更新时间，就是把节点移到最后面，同时更改前后节点关系
        //更改节点关系
        remove(cur);
        //移动到最后面
        insert(cur);
    }
    void insert(Node* cur){ //插入缓存，就是把节点放到最后面
        listtail->pre->next = cur;
        cur->pre = listtail->pre;
        cur->next = listtail;
        listtail->pre = cur;
    }

    void release(){//清除内存，就是从链表头部删除节点，同时也要删除索引
        Node* cur = listpre->next;
        m.erase(cur->key);//删除索引
        remove(cur);
    }

    //要有个结构记录最近最久未使用,使用有序结构即可
    //访问后，如何对优先度进行更新，可以用哈希+链表，把指定节点剔除移到最后
    LRUCache(int capacity) {
        this->capacity = capacity;
        //初始化双向链表结构
        listpre->next  = listtail;
        listtail->pre = listpre;
    }
    
    int get(int key) {
        //这里首先判断是否存在
        if(m.count(key)==0) return -1;
        //存在则进行更新时间
        update(m[key]);
        return m[key]->data;
    }
    
    void put(int key, int value) {
        //首先判断是否存在，存在则进行更新
        if(m.count(key)){
            m[key]->data = value;//更新值
            //更新优先度
            update(m[key]);
            return;
        }
        //不存在进行插入
        if(m.size()==capacity) 
            release();//内存不够,释放一个节点
        Node* cur = new Node(key,value);
        m[key] = cur;//建立索引
        insert(cur);
    }
};