LRU调度算法: C++实现

发布时间:2021-09-20 13:16:56

LRU是Least Recently Used的缩写,即最*最少使用,常用于页面置换算法,是为虚拟页式存储管理服务的。


#include
#include
#include

using namespace std;

struct Node{
int key;
int value;
Node(int k,int v):key(k),value(v){}
};
class LRUCache{
private:
int maxSize; //缓存的最大容量
list cacheList; //用链表保存key的访问顺序,最*访问的Node在链表最前面
map::iterator> mp;//用map储存key和链表的迭代器,方便快速查询key是否存在
public:
LRUCache(int capacity):maxSize(capacity){}

int get(int key){
map::iterator>::iterator it = mp.find(key);
if(it==mp.end()) //NOT Found
return -1;
else{ //Found ,and update node to the front
list::iterator listIter = mp[key];
Node newNode(key,listIter->value);
cacheList.erase(listIter);
cacheList.push_front(newNode);
mp[key] = cacheList.begin();
}
return mp[key]->value;
}

void set(int key,int value)
{
map::iterator>::iterator it = mp.find(key);
if(it==mp.end())
{
if(cacheList.size() == maxSize)
{
mp.erase(cacheList.back().key);
cacheList.pop_back();
}
Node newNode(key,value);
cacheList.push_front(newNode);
mp[key]=cacheList.begin();
}
else
{
list::iterator listIter = mp[key];
Node newNode(key,value);
cacheList.erase(listIter);
cacheList.push_front(newNode);
mp[key] = cacheList.begin();
}
}

void print(){

cout<<"LRUCache :"< for(auto listIter = cacheList.begin();listIter!=cacheList.end();listIter++)
cout<<"Line "<< listIter->key<<" "<value< }

};



测试:


int main()
{
LRUCache LRU(5);
cout<<"输入地址k,值v"< int k,v;
while((cin>>k,k>0))
{
cin>>v;

LRU.set(k,v);

LRU.print();
}

return 0;
}

?

相关文档

  • 如何练习打数字 金山打字通能练习打数字吗
  • 开学第一课读后感范文7篇
  • 粽粑叶是什么植物类别
  • 20201029 Actuator监控
  • 使用GMap.NET类库,实现地图轨迹回放。(WPF版)
  • 真空靴让你变身蜘蛛侠
  • 期待下周Kubernetes1.6正式发布
  • 员工安全承诺书6篇
  • 2020年福建三明医学科技职业学院公开招聘工作人员公告17人
  • 初三数学教学工作总结及工作目标
  • 苹果手机有没被激活怎么办啊
  • 用餐礼仪作文700字 最美餐饮礼大家谈
  • Make the Earth Smile
  • 早泄与阳痿的区别
  • 晴宝贝是什么意思
  • 景观绿化工程施工合同范本
  • 电动机发明人是谁
  • 2013Esri全球用户大会Q&A之ArcGIS for Desktop
  • 怎样正确染发才能减少染发的危害
  • 进口贸易合同模板
  • 电脑经常卡死鼠标不动怎么办
  • 软件设计师上下午试题技巧知识点
  • 商铺物业委托管理协议
  • 部落冲突没绑定怎么找回村庄
  • SpringBoot+SpringMVC+MyBatis整合
  • JVM jmap -histo 简介
  • 2020年社区卫生服务中心年终工作总结
  • 一道风景线初二作文范文600字
  • 春节优秀随笔五篇
  • 初识公有云--公有云的相关概念
  • 猜你喜欢

  • 医职考试用期考核合格证明
  • 最新苏教版小学数学三年级下册精品公开课赛课课件 《认识吨》教学课件 13
  • 《医用基础化学》第三章 缓冲溶液
  • EfficientNetV2震撼发布!更小的模型,更快的训练
  • 陕西秦丰达实业有限公司企业信用报告-天眼查
  • 2019年冀教版数学五年级上册优质课教案一位小数乘整数.
  • 现货华鸾灰兹砑?T4好用吗
  • 咖啡屋创业计划书
  • 活用身边的素材 让数学走进生活
  • 互联网五层模型中每一层分别都有哪些协议
  • 2018-2023年中国金属包装容器制造行业市场发展预测及投资咨询报告
  • 井冈山两种典型森林土壤有机碳密度及其影响因素的比较
  • 公司试用期员工工作计划总结
  • 精选-高考化学基础知识复*方法:把知识融会贯通
  • 学校运动会开幕式主持稿14
  • 深圳市龙岗区坪山镇汤坑村黄二经济合作社企业信息报告-天眼查
  • 天津市峰华辰宇加油站管理有限公司企业信用报告-天眼查
  • 二手经济适用房买卖合同
  • 肝病患者有什么注意事项
  • 入团倡议书
  • Java 优秀开源项目
  • 新行业规范下酒店退房时间的研究
  • 苏科版八年级数学下册12.1-12.2 二次根式,二次根式的乘除 同步练*D卷
  • 联吡啶桥联双核铜配合物修饰玻碳电极对对苯二酚的电催化作用及测定
  • 【知识学*】XX届高考物理知识点速查复*交变电流
  • 2015年上半年湖北省土地估价师《管理法规》:合伙企业登记考试试题
  • 国外创意产品展示PPT课件
  • vsphere exsi 5.5 的正确打开方式
  • 微波炉糕点的做法大全
  • 木守宫的进化型是什么神奇宝贝
  • 阿里云防火墙
  • 氯胺酮产生全身麻醉作用的主要机制是 A.阻断NMDA受体B.激动GAB
  • 2019五年级上册数学教案第二单元 课时1 平行四边形的面积计算ㄏ苏教版精品教育.doc
  • 上海市宝山区杨北彩印厂企业信用报告-天眼查
  • 浅谈骨性关节炎的中医治疗
  • 2018-2019年遵义市桐梓县高桥镇李子小学一年级上册数学第一次模拟月考含答案
  • 扬州大学845水化学2014,2016--2019年考研专业课真题
  • 苏州贝诺易贸易有限公司企业信用报告-天眼查
  • 东怒西怨,夜郎自大-藏头诗
  • 意大利益达切纳有限公司企业信用报告-天眼查
  • 弦外文化创意(北京)有限公司(企业信用报告)- 天眼查
  • 20XX医院护理部年终工作总结
  • 电脑版