LRU的实现(使用list)
2019-08-19 08:47:22来源:博客园 阅读 ()
LRU的实现(使用list)
首先是LRU的定义,LRU表示最近最少使用,如果数据最近被访问过,那么将来被访问的几率也更高。
所以逻辑应该是每次都要将新被访问的页放到列表头部,如果超过了list长度限制,就将列表尾部的元素踢出去。
主要结构,STL中的双向链表结构list。
主要操作有get,表示访问key对应的value,此时要查询双链表,找到key对应value,再将其从list中删除,插入到list的头部。
set, 表示设置对应的key值为value,此时先找到key对应的元素,将其从list中删除,再插入到list的头部。
这里设置了两个辅助函数remove和setHead,分别负责删除元素和将元素加入到list头部。
代码实现如下:
#include <iostream> #include <list> #include <iterator> #include <algorithm> using namespace std; class LRUNode { public: int key,value; LRUNode(int _key,int _value):key(_key),value(_value) { } bool operator==(LRUNode * p) { return key==p->key; } }; class LRU { public: int get(int key); void set(int key,int val); LRU(int _cap):cap(_cap) { } int cap;//代表存放的最大页数 void remove(int key); void setHead(int key,int val); void printLis(); list<LRUNode *> lis; }; void LRU::printLis() { list<LRUNode *>::iterator it; for(it=lis.begin();it!=lis.end();it++) { cout<<(*it)->key<<" "<<(*it)->value<<endl; } cout<<endl; } void LRU::remove(int key) { LRUNode * searchNode=new LRUNode(key,0); list<LRUNode *>::iterator it=find(lis.begin(),lis.end(),searchNode); if(it!=lis.end()) { lis.remove(*it); } } void LRU::setHead(int key,int val) { lis.push_front(new LRUNode(key,val)); } int LRU::get(int key) { LRUNode * searchNode=new LRUNode(key,0); list<LRUNode *>::iterator it=find(lis.begin(),lis.end(),searchNode); if(it!=lis.end()) { remove((*it)->key); setHead((*it)->key,(*it)->value); return (*it)->value; } return -1;//表示没有找到 } void LRU::set(int key,int value) { if(lis.size()>=cap) { lis.pop_back(); } LRUNode * searchNode=new LRUNode(key,0); list<LRUNode *>::iterator it=find(lis.begin(),lis.end(),searchNode); if(it!=lis.end()) { remove(key); setHead(key,value); } else { setHead(key,value); } } int main() { LRU * lru=new LRU(5); lru->set(1,1); lru->printLis(); lru->set(2,2); lru->printLis(); lru->set(3,3); lru->printLis(); lru->set(4,4); lru->printLis(); lru->set(5,5); lru->printLis(); lru->set(6,6); lru->printLis(); lru->set(7,7); lru->printLis(); return 0; }
运行结果:
1 1 2 2 1 1 3 3 2 2 1 1 4 4 3 3 2 2 1 1 5 5 4 4 3 3 2 2 1 1 6 6 5 5 4 4 3 3 2 2 7 7 6 6 5 5 4 4 3 3
原文链接:https://www.cnblogs.com/JsonZhangAA/p/11374439.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- RAID 1 软件实现(Linux 系统) 2020-06-10
- 树莓派使用 OLED 屏显示图片及文字 2020-06-05
- php多版本:已存在php5场景下,编译安装php7,实现apache2.2 2020-06-05
- keepalived 实现LVS负载均衡高可用集群(一) 2020-06-04
- 附020.Nginx-ingress部署及使用 2020-06-02
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash