页面替换算法C++代码
时间: 2024-05-04 18:19:24 浏览: 11
以下是页面替换算法(LRU)的C++代码示例:
```c++
#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;
class LRUCache {
private:
int capacity;
list<int> recent; // 双向链表,存储缓存中的key,头部为最近使用的key,尾部为最不常使用的key
unordered_map<int, int> cache; // 哈希表,存储缓存的key和value
unordered_map<int, list<int>::iterator> pos; // 哈希表,存储每个key在recent中的位置
public:
LRUCache(int capacity) {
this->capacity = capacity;
}
int get(int key) {
if (cache.count(key) == 0) {
return -1;
}
// 将key移动到链表头部
recent.erase(pos[key]);
recent.push_front(key);
pos[key] = recent.begin();
return cache[key];
}
void put(int key, int value) {
if (cache.count(key) == 0) {
if (recent.size() == capacity) {
// 缓存已满,删除最不常使用的key
int least_recent = recent.back();
recent.pop_back();
cache.erase(least_recent);
pos.erase(least_recent);
}
// 将新key插入到链表头部
recent.push_front(key);
pos[key] = recent.begin();
} else {
// 更新value,将key移动到链表头部
recent.erase(pos[key]);
recent.push_front(key);
pos[key] = recent.begin();
}
cache[key] = value; // 更新缓存中的key和value
}
};
int main() {
LRUCache cache(2);
cache.put(1, 1);
cache.put(2, 2);
cout << cache.get(1) << endl; // 1
cache.put(3, 3);
cout << cache.get(2) << endl; // -1
cache.put(4, 4);
cout << cache.get(1) << endl; // -1
cout << cache.get(3) << endl; // 3
cout << cache.get(4) << endl; // 4
return 0;
}
```
在上述代码中,使用了一个双向链表来存储缓存中的key,头部为最近使用的key,尾部为最不常使用的key。同时,使用了两个哈希表来记录每个key在recent中的位置和key和value的对应关系。在get操作中,如果key不在缓存中则返回-1,否则将key移动到链表头部并返回对应的value。在put操作中,如果key不在缓存中则插入到链表头部,如果缓存已满则删除最不常使用的key,然后将新key插入到链表头部。如果key在缓存中,则更新value并将key移动到链表头部。