实现一个 LRU（Least Recently Used）缓存，主要目标是保持最近使用的键值对在前，淘汰最久未使用的条目，并且在 O(1) 时间复杂度内完成访问、插入和删除操作。常见做法是将哈希表（std::unordered_map）与双向链表（std::list）结合使用。哈希表提供快速定位键对应的节点，链表则维护使用顺序。下面给出一个完整可编译的实现示例，并演示其使用方法。
#include <iostream>
#include <unordered_map>
#include <list>
#include <string>
template <typename Key, typename Value>
class LRUCache {
public:
explicit LRUCache(size_t capacity) : capacity_(capacity) {}
// 读取键对应的值，如果存在返回 true 并赋值给 value
bool get(const Key& key, Value& value) {
auto it = cacheMap_.find(key);
if (it == cacheMap_.end()) {
return false; // 缓存未命中
}
// 把访问的节点移到链表前端（最近使用）
touch(it);
value = it->second->second;
return true;
}
// 写入或更新键值对
void put(const Key& key, const Value& value) {
auto it = cacheMap_.find(key);
if (it != cacheMap_.end()) {
// 更新已有条目
it->second->second = value;
touch(it);
return;
}
// 新条目，先检查是否需要淘汰
if (cacheMap_.size() == capacity_) {
evict();
}
// 插入到链表前端
cacheList_.emplace_front(key, value);
cacheMap_[key] = cacheList_.begin();
}
void debugPrint() const {
std::cout << "Cache state (MRU -> LRU):\n";
for (const auto& kv : cacheList_) {
std::cout << kv.first << ":" << kv.second << " ";
}
std::cout << "\n";
}
private:
using ListIt = typename std::list<std::pair<Key, Value>>::iterator;
void touch(typename std::unordered_map<Key, ListIt>::iterator it) {
// 将对应节点移动到链表前端
cacheList_.splice(cacheList_.begin(), cacheList_, it->second);
it->second = cacheList_.begin();
}
void evict() {
// 淘汰链表尾部（最久未使用）
auto last = cacheList_.end();
--last;
cacheMap_.erase(last->first);
cacheList_.pop_back();
}
size_t capacity_;
std::list<std::pair<Key, Value>> cacheList_; // 双向链表
std::unordered_map<Key, ListIt> cacheMap_; // 哈希表映射键 -> 链表迭代器
};
int main() {
LRUCache<std::string, int> cache(3);
cache.put("one", 1);
cache.put("two", 2);
cache.put("three", 3);
cache.debugPrint(); // one:1 two:2 three:3
int value;
cache.get("one", value); // 访问 one，变成 MRU
cache.debugPrint(); // one:1 three:3 two:2
cache.put("four", 4); // 缓存满，淘汰 two
cache.debugPrint(); // four:4 one:1 three:3
if (!cache.get("two", value)) {
std::cout << "\"two\" not found in cache.\n";
}
cache.put("five", 5); // 再次淘汰 three
cache.debugPrint(); // five:5 four:4 one:1
return 0;
}关键点解析
-
双向链表 (
std::list)- 维持键值对的使用顺序。链表头部代表最近使用（MRU），尾部代表最久未使用（LRU）。
splice操作可以在常数时间内把任意节点移动到链表前端。
-
哈希表 (
std::unordered_map)- 将键映射到链表中的迭代器，能够在 O(1) 时间内定位对应节点。
- 结合链表的
splice能够实现快速更新。
-
容量控制
- 当插入新条目且缓存已满时，调用
evict()，移除链表尾部元素并更新哈希表。
- 当插入新条目且缓存已满时，调用
-
通用模板化
- 通过
template，该实现可以用于任何键和值类型，只要键支持哈希（需要 `std::hash `）并且可比较。
- 通过
性能特点
- 时间复杂度：
get、put均为 O(1)。evict也是 O(1)，因为只需弹出尾部元素。
- 空间复杂度：O(capacity)，仅存储最近
capacity个条目。
进一步优化
- 若对线程安全有需求，可在外层使用互斥锁，或者使用
std::shared_mutex实现读写分离。 - 对于大容量缓存，链表占用的内存相对较高，可以改用
std::vector并维护一个双向链表的数组实现（如“LRU Cache with Linked Hash Map”）。 - 若需要对缓存条目做自定义过期策略，可在链表节点中存放时间戳，并定期扫描清理。
以上示例展示了一个完整、易于理解且高效的 LRU 缓存实现，适合在 C++ 项目中直接使用或作为学习参考。