C++实现简单的双向缓存LRU _ list与unordered_map结合【源码】-C++-PHP中文网

c++oding="utf-8" ?>

必须组合使用 std::list 和 std::unordered_map：前者维护访问时序并存储 pair 保证迭代器稳定，后者通过 key→list::iterator 映射实现 o(1) 定位，缺一不可。

c++实现简单的双向缓存lru _ list与unordered_map结合【源码】

为什么不能只用 `std::list` 或只用 `std::unordered_map`

单独用 std::list 查不到某个 key 对应的节点位置，每次 get() 都得遍历——O(N)；单独用 std::unordered_map 又没法维护访问时序，删最久未用的项只能暴力扫 value 找时间戳——还是 O(N)。必须两者协作：unordered_map 存 key → 迭代器映射，list 存 {key, value} 有序排列，才能做到 get() 和 put() 均摊 O(1)。

`list` 节点该存什么？别存裸指针

存裸指针（比如 pair<const k v></const>）看似省空间，但一旦 list 重分配内存（如扩容、splice），所有迭代器失效，unordered_map 里存的迭代器就变悬垂指针，后续解引用直接 UB。正确做法是存完整键值对：std::list<:pair v>></:pair>。虽然多占点内存，但迭代器稳定，且 C++11 后 move 语义让插入/移动开销可控。

C++14

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

下载

不要写 list<pair k v>></pair> —— const K 会让 list::splice() 失败（需可移动/可赋值）
节点结构推荐： std::pair<k v></k>，key 和 value 都非 const
插入新节点后，立刻用 list::begin() 获取其迭代器存入 map，别依赖中间变量

`unordered_map` 的 value 类型必须是 `list<...>::iterator</...>`

这是双向缓存的核心纽带。map 不存 value 副本，只存 list 中对应节点的迭代器，靠它实现 O(1) 定位 + O(1) 搬运。注意几个易错点：

声明类型要写全：std::unordered_map<k std::list v>>::iterator></k>，别漏掉嵌套作用域
插入新节点后，list::push_front() 返回的是 iterator，直接存进 map 即可，别用 &*it 取地址
调用 list::erase(it) 后，原迭代器立即失效，必须同步从 map 中 erase(key)，否则下次 get 会解引用已销毁迭代器

// 示例：put 操作关键片段
auto it = cache_list.emplace(cache_list.begin(), key, value);
cache_map[key] = it; // 存的是 iterator，不是指针

容量超限时删谁？别删 `cache_list.back()` 就完事

删尾节点前，必须先从 cache_map 中移除对应 key，否则残留的迭代器指向已释放内存。更隐蔽的问题是：如果 put() 时 key 已存在，要先删旧节点再插新节点，否则 map 里还挂着旧迭代器，而旧节点已被 erase，map 中的迭代器就成悬垂状态。

每次 put(key, value) 先查 map：存在则 cache_list.erase(cache_map[key]) + cache_map.erase(key)
插入新节点后，检查 size() > capacity，若是，取 cache_list.back().first 得到待删 key，再 cache_map.erase(该 key)，最后 cache_list.pop_back()
别用 cache_list.size() > capacity 判定——频繁调用 size() 在某些 libstdc++ 实现里是 O(N)，改用计数器 int _size 维护