程序笔记
发布时间：2022-07-11 发布网站：大佬教程 code.js-code.com
大佬教程收集整理的这篇文章主要介绍了LRU最近最少使用代码实现，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
LRU是指长期没有被使用的数据在未来使用的概率不大，当数据所占内存达到一定的阈值，要移除最近最少使用的数据，为新加入的数据腾出空间。
LRU使用哈希+链表的结构，如图所示，我们假设容量为2，依次插入数据1和数据2；
当访问了某个结点，就将结点放在链表的最右端。如图所示我们访问了结点1，就将结点1移到链表的最右端。
当达到了容量上限再插入新数据时，就将最近最少使用的数据移除，如图所示，我们插入结点3，在插入之前将结点2移出去。
详细代码如下：get()用来访问元素，set()用来添加元素。
@H_
618_26@
class LRU
{
public:
LRU(int k):m_capcity(
k){};
list<
int>@H_69_29
@mylist;
un
ordered_map<
int, pair<
int, list<
int>::iterator>>
hashmap;
void insert(
int key,
int value)
{
mylist.push_BACk(key);
hashmap[key]=make_pair(value, --@H_69_29
@mylist.end()
);
}
int get(
int key)
//每访问一次将该结点移到链表最右边
{
auto it=hashmap.find(key
); //在哈希表中找key
if(it
!=hashmap.end())
//找到了
{
mylist.erase(it->second.second
); //删除链表当前结点
mylist.push_
BACk(key
);//重新在尾部删除
hashmap[key].second=(--mylist.end()
); //修改哈希表中的指针部分，让它重新指向链表的尾部
return it->
second.first;
}
return -
1;
}
void set(
int key,
int value)
{
if(
get(key)
!=-
1)
//原来链表中有key,只需修改value
{
hashmap[key].first=
value;
return;
}
if(hashmap.size()<m_capcity)
//还有空间，直接插入
insert(key, value);
else//将链表最左边的结点连同哈希表结点一起删除
{
int removekey=@H_69_29
@mylist.front(
);
mylist.pop_front(
);
hashmap.erase(removekey
);
insert(key,
value);
}
}
private:
int m_capcity
}
大佬总结
以上是大佬教程为你收集整理的LRU最近最少使用代码实现全部内容，希望文章能够帮你解决LRU最近最少使用代码实现所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
