LRU算法

一种按时序来淘汰的缓存淘汰策略！！！

概念

LRU的全称是Least Recently Used，即最近最少使用，我们认为最近使用过的数据是有用的，很久没有使用过的数据是无用的，内存满了就先删除那些很久没有用过的数据。

• 显然cache里面的元素要有时序，支持快速查找，支持在任意位置插入和删除元素；
• 用节点来表示每一个键值对key-value；
• 可以结合双向链表与哈希表，链表里面是节点，哈希表存储key及链表中对应的节点；
• 双向链表中靠头部元素是最久未使用的，靠尾部元素是最近使用的；
• 添加元素时先查看缓存容量，只能从尾部插入；
• 若添加新元素时遇到相同key值，只需更新value值和将链表中节点移动到尾部；
• 缓存容量不足时从链表头部删除节点，并且删除umap中对应节点；
• 访问某元素后要将该节点位置移动到链表尾部；
• umap中节点的变动只发生在添加新节点和缓存容量不够时；
• 注意移除与删除列表中节点的区别，移除只是离开链表，删除是销毁这个申请的节点内存；

自定义双向链表，哈希表存节点

struct Node {
    int key, value;
    Node* prev;
    Node* next;
    //必须添加下面两个构造函数
    Node() : key(0), value(0), prev(nullptr), next(nullptr) {}
    Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
struct NodeList {
    Node* head;
    Node* tail;
    NodeList() {
        //必须要new
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->prev = head;
    }
    //添加节点到链表尾部
    void addToTail(Node* node) {
        node->prev = tail->prev;
        tail->prev->next = node;
        node->next = tail;
        tail->prev = node;
    }
    //从链表中移除某个节点，前提是这个节点必须存在于链表中
    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    //删除链表中最久未使用的节点，即靠近头部的那个节点
    int cleanOneCache() {
        Node* tmp = head->next;
        int key = tmp->key;
        remove(tmp);
        delete tmp;
        return key;
    }
    //使某个被访问的元素到链表尾部
    void makeItRecently(Node* node){
        remove(node);
        addToTail(node);
    }
};
class LRUCache {
private:
    NodeList list;
    unordered_map<int, Node*> umap;
    int capacity;
public:
    LRUCache(int cap) {
        capacity = cap;
    }
    
    int get(int key) {
        if(umap.find(key) == umap.end()) {
            return -1;
        } else {
            Node* node = umap[key];
            int value = node->value;
            //更新链表中节点位置
            list.makeItRecently(node);
            return value;
        }
    }
    
    void put(int key, int value) {
        if(umap.find(key) != umap.end()) {
            Node* cur = umap[key];
            //更新节点中的value值
            cur->value = value;
            //更新链表中节点位置
            list.makeItRecently(cur);
        } else {
            //先查看缓存容量是否充足
            if(capacity == 0) return;
            if(umap.size() == capacity) {
                int k = list.cleanOneCache();
                umap.erase(k);
            }
            //添加新节点到链表和umap中
            Node* node = new Node(key, value);
            list.addToTail(node);
            umap[key] = node;
        }
    }
};

使用STL链表，哈希表存迭代器

class LRUCache {
public:
    LRUCache(int capacity) : capacity_(capacity) {}
    
    int get(int key) {
        if (umap_.find(key) == umap_.end()) {
            return -1;
        }
        auto it = umap_[key];
        int val = it->second;
        lruList_.erase(it);
        lruList_.emplace_front(key, val);
        umap_[key] = lruList_.begin();
        return val;
    }
    
    void put(int key, int value) {
        if (umap_.find(key) != umap_.end()) {
            lruList_.erase(umap_[key]);
        } else {
            if (umap_.size() == capacity_) {
                umap_.erase(lruList_.back().first);
                lruList_.pop_back();
            }
        }
        lruList_.emplace_front(key, value);
        umap_[key] = lruList_.begin();
    }
private:
    list<pair<int, int>> lruList_; // 链表 头部进入 尾部离开
    unordered_map<int, list<pair<int, int>>::iterator> umap_;
    int capacity_;
};