下面是一个 C++ 中 LRU（Least Recently Used）缓存的实现示例。我们将使用 std::unordered_map 来存储键值对，同时用 std::list 来维护元素的顺序。
C++ 实现
#include <iostream>
#include <unordered_map>
#include <list>
class LRUCache {
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
if (cacheMap.find(key) == cacheMap.end()) {
return -1; // 如果不存在，返回 -1
}
// 移动到最近使用的位置
updateUsage(key);
return cacheMap[key]->second;
}
void put(int key, int value) {
if (cacheMap.find(key) != cacheMap.end()) {
// 更新已存在的值并移动到最近使用的位置
cacheMap[key]->second = value;
updateUsage(key);
} else {
if (cacheList.size() >= capacity) {
// 超出容量，移除最久未使用的项
int lruKey = cacheList.back().first;
cacheList.pop_back();
cacheMap.erase(lruKey);
}
// 插入新项
cacheList.push_front({key, value});
cacheMap[key] = cacheList.begin();
}
}
private:
using Pair = std::pair<int, int>;
std::list<Pair> cacheList; // 用于保持顺序的链表
std::unordered_map<int, decltype(cacheList.begin())> cacheMap; // 存储键和对应列表位置的映射
int capacity;
void updateUsage(int key) {
auto it = cacheMap[key];
Pair item = *it;
// 将当前项移除并重新插入到前面表示最近使用过
cacheList.erase(it);
cacheList.push_front(item);
// 更新 map 中对应的迭代器位置
cacheMap[key] = cacheList.begin();
}
};
// 示例用法：
int main() {
LRUCache lru_cache(2); // 容量为2
lru_cache.put(1, 1); // 缓存是 {1=1}
lru_cache.put(2, 2); // 缓存是 {1=1, 2=2}
std::cout << lru_cache.get(1) << std::endl; // 返回 1
lru_cache.put(3, 3); // 淘汰键 2，缓存是 {1=1, 3=3}
std::cout << lru_cache.get(2) << std::endl; // 返回 -1 (未找到)
lru_cache.put(4, 4); // 淘汰键 1，缓存是 {3=3, 4=4}
std::cout << lru_cache.get(1) << std::endl; // 返回 -1 (未找到)
std::cout << lru_cache.get(3) << std::endl; // 返回 3
std::cout << lru_cache.get(4) << std::endl; // 返回 4
return 0;
}
工作原理：
- 使用
std::list来保持元素的顺序，以便能够快速删除和插入元素。 - 使用
std::unordered_map保存每个键及其在链表中的位置，这样可以在 O(1) 的时间内访问。 - 在
get方法中，当获取一个元素时，我们会将其标记为最近使用，通过将它从链表中删除并插入到头部来完成。 - 在
put方法中，如果缓存达到最大容量，则移除最后一个（最不常用）元素。
这种实现方式同样提供了平均 O(1) 的时间复杂度，非常适合用于 LRU 缓存。
内容由零声教学AI助手提供，问题来源于学员提问
