LRU算法C++实现
编辑:谯胜平 分类:程序与算法 标签:LRU 发布时间:2021-05-12 浏览次数:893次
1、思路:LRU算法的思想这里就不介绍了,重点说一下实现方法。使用双向循环链表保存当前驻留集中的页面,使用unordered_map<int, LinkNode*>记录页面值page与节点地址的映射关系(方便根据page查找结点在链表中是否存在)。
当访问某个页面上时,先查看链表中是否有指定的页面,如果没有,则将此页面插入到双向循环链表头部,并将page和节点地址保存到unordered_map中;
如果链表中已经存在指定的页面,则通过unordered_map查找到指定节点地址,并将节点从链表中摘下并插入到链表头部。
每次访问,都需要对链表进行检查,如果链表长度超过了驻留集大小,则删除链表尾结点并删除unordered_map中的对应节点地址和page值;
2、代码:
#include<iostream> #include<unordered_map> using namespace std; struct LinkNode{ int page; LinkNode *pre, *next; LinkNode(){ pre = nullptr; next = nullptr; page = -1; } }; class LRU{ private: LinkNode *head; unordered_map<int, LinkNode*> addr; int LEN; public: LRU(int len){ head = new LinkNode; head -> next = head; head -> pre = head; LEN = len; } //访问某个页面 void read(int page); //显示当前驻留集中的页面 void display(); //更新驻留集中的页面,如果当前页面过多,则删除链表尾部节点 void update(); ~LRU(){ delete head; } }; void LRU::update(){ if(addr.size() > LEN){ //删除尾结点 LinkNode *p = head -> pre; p -> pre -> next = head; head -> pre = p -> pre; addr.erase(p -> page); delete p; } } void LRU::read(int page){ //在链表中没有发现,则将当前访问的数据插入链表首部 if(addr.find(page) == addr.end()){ LinkNode *now = new LinkNode; now -> page = page; now -> next = head -> next; head -> next -> pre = now; head -> next = now; //记录下当前page的地址 addr[page] = now; }else{ //将当前访问的页面摘下放到头部 LinkNode *now = addr[page]; addr[page] -> pre -> next = addr[page] -> next; addr[page] -> next -> pre = addr[page] -> pre; now -> next = head -> next; head -> next -> pre = now; head -> next = now; } //更新链表 update(); } void LRU::display(){ LinkNode *p = head -> next; while(p != head){ cout << p -> page << " "; p = p -> next; } cout << endl; } int main(){ cout << "请输入驻留集大小:"; int mem; cin >> mem; LRU lru(mem); cout << "\n请输入访问页面(-1退出):"; int key; cin >> key; while(key != -1){ lru.read(key); cout << "当前驻留集页面:"; lru.display(); cout << endl; cout << "请输入访问页面(-1退出):"; cin >> key; } return 0; }
3、运行截图:
热门文章
文章标签
- web(1)
- 数据库索引(1)
- 栈(1)
- const(2)
- #define(1)
- 虚函数(1)
- 反转链表(2)
- 深拷贝(1)
- 浅拷贝(1)
- 快速排序(1)
- 线程(1)
- 线程模型(1)
- (41)
- LRU(1)
- C++11(1)
- 一致性哈希算法(1)
- CPU(1)
- malloc(1)
- 迭代器(1)
- linux下编译(1)
- 类模板(1)
- git(1)
- Linux(2)
- 学科评估(2)
- scanf(2)
- gets(1)
- getchar(1)
- 考研经验(1)
- printf(1)
- mysql(2)
- STL(2)
- 富文本编辑器(1)
- 闰月(1)
- vector(1)
- CA(3)
- HTTPS(1)
- 晴天的魔法乐园(1)
- 单例模式(1)
- 谷歌(1)
- unzip(1)
- gcc(1)
- ubuntu(1)
- getline()(1)
- 作息时间表(1)
友情链接