C++实现LRU缓存淘汰机制 _ 哈希表与双向链表结合【源码】-C++-PHP中文网

不能只用 std::unordered_map 实现 LRU，因其无法在 O(1) 内移动节点至表头以维护访问顺序；必须结合双向链表（如 std::list）并通过 splice 避免迭代器失效，配合哈希表实现 get/put 均为 O(1)，且需校验 capacity 合法性。

c++实现lru缓存淘汰机制 _ 哈希表与双向链表结合【源码】

为什么不能只用 `std::unordered_map` 实现 LRU？

因为哈希表本身不记录访问顺序，std::unordered_map 查找是 O(1)，但无法在常数时间内把某个 key “移到最近使用位置”。LRU 的核心操作——“访问即置顶”和“淘汰最久未用项”，必须支持快速定位 + 快速移动节点。单靠哈希表做不到，必须搭配能 O(1) 插入/删除任意节点的结构，双向链表正好满足。

`std::list` 能直接用吗？注意迭代器失效问题

可以，但要小心：每次 list::erase(iterator) 后，该迭代器立即失效；而如果你把 list::iterator 存在哈希表里（比如 unordered_map::iterator>），那每次从链表中移除节点后，对应 map 里的 iterator 就成了悬空指针——下次再解引用会崩溃。

实操建议：

用 list::splice() 把节点从中间“剪切”并“粘贴”到头部，避免 erase + push_front，这样迭代器保持有效
或者改用自定义双向链表（含 prev/next 指针），自己管理节点生命周期，更可控
若坚持用 std::list，务必在每次 erase 后同步更新 map 中的 iterator，但逻辑易错，不推荐

如何让 `get()` 和 `put()` 都做到 O(1)？

关键在于哈希表与链表的双向绑定：

哈希表存 key → node*（或 list::iterator），提供 O(1) 定位
链表节点存 key 和 value，头部为最近使用，尾部为最久未用
get(key)：查哈希表 → 找到节点 → 用 splice 移到链表头 → 返回 value
put(key, value)：已存在则更新 value 并 splice 到头；不存在则新建节点插头，若超容，删尾节点并从哈希表 erase 对应 key

示例片段（简化）：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

auto it = cache_map.find(key);
if (it != cache_map.end()) {
    cache_list.splice(cache_list.begin(), cache_list, it->second); // O(1) 移动
    it->second->second = value; // 更新值
} else {
    cache_list.emplace_front(key, value);
    cache_map[key] = cache_list.begin();
    if (cache_list.size() > capacity) {
        auto& tail = cache_list.back();
        cache_map.erase(tail.first);
        cache_list.pop_back();
    }
}

容量为 0 或负数时怎么处理？

很多实现忽略这个边界，结果一设 capacity = 0 就无限插入、不淘汰，缓存失控。

正确做法：

构造时对 capacity 做校验：if (capacity
在 put() 中，先判断 capacity == 0：此时所有 put 都应等效于“清空旧值 + 不缓存新值”，即直接 erase 原 key（如有），且不插入新节点
注意：capacity = 0 时 get() 仍应返回 -1（或默认值），但不触发任何链表操作

这个点容易被跳过，但线上环境一旦配置错误，会导致内存持续增长。