LRU Cache

一、介绍

0.LRU Cache引例

你是一个热爱技术的人，你每天都要去教室看书学习，我们知道，计科当中很多知识都是有关联的，有可能你看着一本有关《程序设计》的书，你思考某个设计方案时，你就联想到了《数据库》当中的表的连接相关的知识

然后你就再去查阅一下那里的知识，综合起来进行关联思考，从而能够站在《数据库》的角度来理解这里程序设计的方案

因此你去教室就需要带上很多书，以备不时之需

而书包的容量是有限的，而且你发现最近你最常访问的书被你再次访问的概率是更大的，而长时间未曾访问的书被再次访问的概率是更小的【时间局部性原理】，

因此某天你设计出了一个智能背包，这个智能背包能够在背包容量到达限制时选择最近最少使用的书进行淘汰，以便为新的书腾出空间

这个智能背包就是LRU Cache

1.LRU Cache介绍

LRU（Least Recently Used） Cache：最近最少使用，是一种Cache替换算法。

它的核心思想是：
当缓存容量达到上限时，优先淘汰那些最近最少使用的【最久未使用的】数据

这个策略是基于一种假设：
如果一个数据项在最近一段时间内没有被访问，那么在将来，它被访问的概率也很小

2.Cache

缓存是用来协调两个数据传输效率不同的介质之间的一个中间层
比如：计算机存储金字塔

二、实现

牵扯到查找，那必然是通过一个key来查找一个value
所以我们的LRU Cache是<key,value>型的数据

1.操作

对于Cache的操作无非就三种：
put，get和replace（满了的话才替换）

void put(key_type key,value_type val);value_type get(key_type key);void replace(key_type key,value_type val);

下面我们来思考实现方案：

2.unordered_map – O(1)的get,put

既然存放的是一个<k,v>型的数据，那么势必就需要一个支持快速查找的一个<k,v>型的关联式容器，首选哈希表unordered_map

有了unordered_map之后，我们就可以实现O(1)的put和get

但是replace我们无法实现，因为我们不知道最近最少使用的那个元素是谁

所以单纯只有哈希表是不行的
我们必须要时刻维护最近最少使用的元素的一个状态，也就是维护所有元素的最近一次访问次序

3.如何维护次序，以实现replace

想要知道如何编程维护次序，首先要知道如何维护次序【什么时候维护次序，怎样维护次序】


因此我们用list来维护次序

list<pair<key_type,value_type>> data_list;

下面来看如何才能通过哈希表快速找到对应数据

unordered_map<int,list<pair<int,int>>::iterator> data_hash;

三、代码

因为这个验证不好搞，所以我们用一下Leetcode上面的具体题目充当测试吧：
LCR 031. LRU 缓存

1.get

步骤：

1. 从哈希表当中拿到list的迭代器iter_list
2. 根据iter_list拿到返回值value
3. 从链表当中删除该iter_list
4. 向链表尾插数据（用参数key和返回值value组成的一个pair）
5. 更新哈希表当中的迭代器iter_hash【否则有迭代器失效问题】

1.从哈希表当中拿到list的迭代器iter_list

auto iter_hash=data_hash.find(key);
if(iter_hash==data_hash.end())//该数据不在cache当中，返回-1
{return -1;
}
//注意：这里存在迭代器失效的风险
iter_type iter_list=iter_hash->second;//拿到list的迭代器

2.根据iter_list拿到返回值value

int value=iter_list->second;//拿到key所对应的value

3.从链表当中删除该iter_list

data_list.erase(iter_list);

4.向链表尾插数据

data_list.push_back({key,value});

5.更新哈希表当中的迭代器iter_hash

因为链表必定不为空，所以这里无需判断是否为空即可使用
但是为了代码健壮性，判断一下也行

if(!data_list.empty())data_hash[key]=std::prev(data_list.end());

6.完整代码

int get(int key) 
{auto iter_hash=data_hash.find(key);if(iter_hash==data_hash.end())//该数据不在cache当中，返回-1{return -1;}//先拿到迭代器的值,然后删除该迭代器//注意：这里存在迭代器失效的风险iter_type iter_list=iter_hash->second;//拿到list的迭代器int value=iter_list->second;//拿到key所对应的valuedata_list.erase(iter_list);//然后链表尾插新数据data_list.push_back({key,value});//更新哈希表当中的迭代器//end是最后一个元素的下一个位置，所以 std::prev(data_list.end());if(!data_list.empty())data_hash[key]=std::prev(data_list.end());return value;
}

不过也可以用list的splice【粘接】这个函数，这个函数直接转移迭代器，并不会删除迭代器：
将链表x当中的迭代器i转移到调用该函数的链表的position迭代器位置

auto iter=list1.begin();
list2.splice(list2.begin(), list1, iter);这个函数的意思就是:
将list1的iter这个迭代器转移到list2的begin()位置

7.splice小例子:

int main()
{list<int> lt1 = {1, 2, 3, 4, 5}, lt2;for (auto iter = lt1.begin(); iter != lt1.end();){auto it = std::next(iter);lt2.splice(lt2.end(), lt1, iter);cout << "lt1[" << lt1.size() << "]" << endl;for (auto &e : lt1){cout << e << " ";}cout << endl;cout << "lt2[" << lt2.size() << "]" << endl;for (auto &e : lt2){cout << e << " ";}cout << endl;iter = it;}return 0;
}

2.put

put不仅仅可以用来插入数据，也可以用来更新数据
步骤：

1. 查找该值是否在哈希表当中存在
2. 若存在则删除那个值
3. 判断缓存是否满了，若满了则进行替换
4. 替换：
5. 拿到链表队头元素的key值
6. 链表头删
7. 在哈希表当中删除那个值
8. 链表尾插新数据
9. 哈希表更新新数据（虽然insert效率高，但是insert不能修改元素，而为了代码的健壮性，所以用operator[]）

1.查找并删除

//因为iter_hash除了这个作用域就迭代器失效了，所以为了代码健壮性，这里给他一个局部作用域，让他提前销毁
{// 先查找该值在哈希表当中是否存在auto iter_hash=data_hash.find(key);if(iter_hash!=data_hash.end()){// 删除那个值iter_type iter_list=iter_hash->second;data_list.erase(iter_list);data_hash.erase(iter_hash);}
}

2.替换

//缓存满了，需要替换 : 
if(data_hash.size()==_capacity)
{// 1. 拿到链表的队头元素的delete_key值int delete_key=data_list.front().first;// 2. 链表头删data_list.pop_front();// 3. 在哈希表当中删除delete_key值对应的数据data_hash.erase(delete_key);
}

3.新增

// 链表尾插
data_list.push_back({key,value});
// 迭代器存到哈希表当中
data_hash[key]=--data_list.end();

4.完整代码

void put(int key, int value) 
{//因为iter_hash除了这个作用域就迭代器失效了，所以为了代码健壮性，这里给他一个局部作用域，让他提前销毁{// 先查找该值在哈希表当中是否存在auto iter_hash=data_hash.find(key);if(iter_hash!=data_hash.end()){// 删除那个值iter_type iter_list=iter_hash->second;data_list.erase(iter_list);data_hash.erase(iter_hash);}}//缓存满了，需要替换 : if(data_hash.size()==_capacity){// 1. 拿到链表的队头元素的delete_key值int delete_key=data_list.front().first;// 2. 链表头删data_list.pop_front();// 3. 在哈希表当中删除delete_key值对应的数据data_hash.erase(delete_key);}// 链表尾插data_list.push_back({key,value});// 迭代器存到哈希表当中data_hash[key]=--data_list.end();
}

四、模板化

那我们下面就把key_type和value_type模板化

不过请注意：在我们模板化的这里，如果数据不在cache中，则返回value_type的默认值
而题目要求返回-1，只有这一点不同而已

template<class key_type,class value_type>
class LRUCache_template {
public:LRUCache_template(int capacity) :_capacity(capacity){}value_type get(key_type key) {auto iter_hash=data_hash.find(key);if(iter_hash==data_hash.end())//该数据不在cache当中，返回value_type的默认值{return value_type();}//先拿到迭代器的值,然后删除该迭代器//注意：这里存在迭代器失效的风险iter_type iter_list=iter_hash->second;//拿到list的迭代器value_type value=iter_list->second;//拿到key所对应的value// splice的话就不会迭代器失效了//void splice (iterator position, list& x, iterator i);// 将链表x当中的迭代器i转移到  当前链表的position位置data_list.splice(data_list.end(),data_list,iter_list);return value;}void put(key_type key, value_type value) {{// 先查找该值在哈希表当中是否存在auto iter_hash=data_hash.find(key);if(iter_hash!=data_hash.end()){// 删除那个值，然后重新插入iter_type iter_list=iter_hash->second;data_list.erase(iter_list);data_hash.erase(iter_hash);}}//缓存满了，需要替换 : if(data_hash.size()==_capacity){// 1. 拿到链表的队头元素的delete_key值int delete_key=data_list.front().first;// 2. 链表头删data_list.pop_front();// 3. 在哈希表当中删除delete_key值对应的数据data_hash.erase(delete_key);}// 链表尾插data_list.push_back({key,value});// 迭代器存到哈希表当中data_hash[key]=std::prev(data_list.end());}
private:using iter_type=list<pair<key_type,value_type>>::iterator;//链表： 头：最旧   尾：最新list<pair<key_type,value_type>> data_list;unordered_map<key_type,iter_type> data_hash;int _capacity;
};