文章目录

• 一、什么是LRU算法
• 二、LRU的实现

一、什么是LRU算法

因为我们的磁盘->内存->高速缓存->cpu之间的速度不同，所以我们设置了缓存
缓存空间满了之后，更新数据，我要进入，谁出去呢？
LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。，将最近最少被使用的算法替换出去。（包括读和写）

二、LRU的实现

LRU缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

要调整_LRUList中key的位置到头部，更新顺序
但是我们不知道数据在哪里，只能遍历查找，这个就变成了O(N)
我们找到了数据，我们还需要知道在链表中的位置
所以我们下面用了unorder_map作为映射，记录当前的key在我们链表中对应的位置
然后用一个list来记录我们题目要求的

class LRUCache {
public:LRUCache(int capacity) :_capacity(capacity){}int get(int key) {//返回_hashmap中存key的迭代器auto ret=_hashMap.find(key);//如果存在if(ret !=_hashMap.end()){//更新key对应的值的位置//ret的second是对应的值在链表里面的迭代器的位置LtIter it=ret->second;//splice 转移节点_LRUList.splice(_LRUList.begin(),_LRUList,it);//ret->second找到的是在链表中的迭代器的位置再->second就是找到第二个元素也就是存的具体的数据return  ret->second->second;}else{return -1;}}void put(int key, int value) {//1、新增//2、更新auto ret=_hashMap.find(key);//如果当前的缓存中并没有存过这个retif(ret ==_hashMap.end()){//如果满了，就需要先删除LRU的数据if(_capacity==_hashMap.size()){//根据题目的示例，我们需要删除尾部的数据pair back=_LRUList.back();//根据back.first也就是键值在map中删除_hashMap.erase(back.first);//删除链表的最后一个节点_LRUList.pop_back();}//将新的键值添加到我们的链表最前面_LRUList.push_front(make_pair(key,value));//map中存的是key值和对应的在链表中的迭代器_hashMap[key]=_LRUList.begin();}//如果当前的缓存中已经存过了这个retelse{//更新key对应的值的位置//找到这个key值在链表中对应的位置LtIter it=ret->second;//更新这个key对应的键值it->second=value;//更新//splice 转移节点//将这个刚刚访问过的结点转移到链表的头部_LRUList.splice(_LRUList.begin(),_LRUList,it);}}
private://hash保证查找更新是O（1）typedef list>::iterator LtIter;unordered_map_hashMap;//LRU 假设尾部的数据就是最近最少用list> _LRUList;//最大容量size_t _capacity;
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/