用c++编写lru程序
时间: 2023-08-28 22:03:19 浏览: 45
下面是一个简单的C++实现LRU算法的代码:
```c++
#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;
class LRUCache {
private:
int capacity;
unordered_map<int, list<pair<int, int>>::iterator> cache;
list<pair<int, int>> lru; // 存储 key-value pair,pair 的第一个元素为 key,第二个元素为 value
public:
LRUCache(int capacity) {
this->capacity = capacity;
}
int get(int key) {
if (cache.find(key) == cache.end()) {
return -1;
}
// 把当前访问的 key 移动到 lru 列表的头部
lru.splice(lru.begin(), lru, cache[key]);
return cache[key]->second;
}
void put(int key, int value) {
if (cache.find(key) == cache.end()) {
// 如果 key 不存在,则插入一个新的键值对
if (lru.size() == capacity) {
// 如果 lru 列表已经满了,则删除最久未使用的键值对(即 lru 列表的尾部)
int del_key = lru.back().first;
cache.erase(del_key);
lru.pop_back();
}
lru.push_front(make_pair(key, value));
cache[key] = lru.begin();
} else {
// 如果 key 存在,则更新其对应的 value,并把当前访问的 key 移动到 lru 列表的头部
cache[key]->second = value;
lru.splice(lru.begin(), lru, cache[key]);
}
}
};
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;
}
```
LRU算法的主要思路是维护一个双向链表(即lru),链表的头部存储最近访问过的键值对,链表的尾部存储最久未使用的键值对。同时,使用一个哈希表(即cache)来存储每个键值对在lru中的位置。每次访问一个键值对时,都把它移动到lru的头部;每次插入一个新的键值对时,都把它插入到lru的头部;如果lru已经满了,则删除最久未使用的键值对(即lru的尾部)。