C++实现LRU缓存

链接：设计LRU缓存结构__牛客网
来源：牛客网

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能:
1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
2. get(key)：如果关键字 key 存在于缓存中，则返回key对应的value值，否则返回 -1 。
3. set(key, value)：将记录(key, value)插入该结构，如果关键字 key 已经存在，则变更其数据值 value，如果不存在，则向缓存中插入该组 key-value ，如果key-value的数量超过capacity，弹出最久未使用的key-value

要求：函数set和get必须以O(1)的方式运行

第一次遇到这道题竟然是在笔试中，当时真的不太清楚要设计一个怎样的数据结构！

其实是这样的：

LRU算法简单说就是，缓存大小有限，超过缓存大小时去掉最久远没有使用的数据，如果使用了数据，当前使用的数据被认为最近一次使用的。

我们要存储的数据类型是键值对，用一个链表存储，节点类型是键值对，节点位置越靠前越符合最近使用这个描述。

调用get和set都算使用了这个key，如果链表中没有这个数据直接头插，如果有，先删除再头插，当链表节点数超过缓存大小，将链表尾部删除。在链表插入删除节点的复杂度都是O(1);

但想要判断链表中是否有这个key也要求O(1),所以用一个哈希表存key和链表节点的映射关系

哈希表和链表里有没有某个key是一致的，哈希表里有某个key就可以根据映射关系拿到这个key在链表中的节点进行操作，哈希表的操作也是O（1）这样就满足要求了。

具体实现：

class Solution {
public:
    int cap;
    list> dataList;
    unordered_map>::iterator> mp;
    
    Solution(int capacity){
        cap = capacity;
    }
    
    int get(int key) {
        if(mp.find(key) != mp.end()) {
            int value = mp[key]->second;
            dataList.erase(mp[key]);
            dataList.push_front(make_pair(key, value));
            mp[key] = dataList.begin();
            return value;
        } else return -1;
    }
    
    void set(int key, int value){
        if(mp.find(key) != mp.end()) {
            dataList.erase(mp[key]);
        } else if(dataList.size() == cap) {
            mp.erase(dataList.back().first);
            dataList.pop_back();
        }
        dataList.push_front(make_pair(key, value));
        mp[key] = dataList.begin();
    }
};