LRU算法list链表实现
2021-04-14 03:26
标签：http begin 取数据 https tps 读取数据 数据 end recent LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。 1存在 存在就比较简单了，直接取出数据，页面数据不变，并把这个结点放在list链表最前面，删除原来位置的节点 2不存在 cache满 把最靠后的页面删除，然后把需要的页面放到最前的位置 cache不满 直接去读取数据，然后把他放在最前的位置 LRU算法list链表实现 标签：http begin 取数据 https tps 读取数据 数据 end recent 原文地址：https://www.cnblogs.com/-citywall123/p/13338648.html#include
void fun(std::listint>&L,int x)
{
for(std::listint>::iterator it=L.begin();it!=L.end();it++)
{
if(*it==x)
{
L.push_front(x);
L.erase(it);
return;
}
}
std::cout"发生缺页中断 "std::endl;
L.pop_back();
L.push_front(x);
}
int main()
{
std::listint>L;
int sum, n, i,x;
sum = 0; //初始cache内没有数据
std::cin>>n; //读入页数
while (true)
{
scanf("%d", &x);
if (x 0)
{
break;
}
else
{
if (sum //cache未满，放至后面
{
L.push_front(x);
std::cout"发生缺页中断 "std::endl;
sum += 1; //并对cache+1
}
else
{
fun(L,x);
}
}
}
return 0;
}
C++ list 因为内部就是双向链表