C++如何实现简单的LRU缓存淘汰策略？（unordered_map+list）

正确做法是unordered_map存list::iterator，而非value本身，以实现o(1)定位、移动与删除；需校验capacity≤0边界，禁用deque因其中间操作会使迭代器失效。

为什么不用 std::list 的迭代器直接存 unordered_map？

因为 std::list 重分配节点时迭代器不会失效，但插入/删除中间节点后，你存的迭代器仍有效——问题不在有效性，而在「怎么快速定位到要淘汰的尾节点」。真正坑是：如果只用 unordered_map<key value></key> + 独立维护一个 list<key></key>，每次访问都要把对应 key 从 list 中间删掉再 push_front，而 list 的 erase 需要先 find，O(n) 查找直接毁掉 LRU 的 O(1) 期望性能。

正确做法是让 unordered_map 存的是 list<pair value>>::iterator</pair>，这样通过 key 一次哈希就能拿到 list 中的精确位置，erase + splice 到头部都是 O(1)。

• unordered_map 的 value 类型必须是 list<...>::iterator</...>，不是 value 本身
• list 要存完整 pair<key value></key>，不能只存 value，否则迭代器解引用后拿不到 key，无法在 map 中反查
• 别用 list::end() 当作“尾部”，要用 --list.end() 或维护一个指向尾的迭代器，避免越界

get() 和 put() 中如何安全更新 list 顺序？

核心就两条：访问命中时，把对应节点移到 list 头；写入新 key 且超容时，删 list 尾（最久未用），并从 map 中 erase 对应 key。难点在「移动节点」不是拷贝值，而是用 splice() 原地搬运迭代器。

• 用 cache_list.splice(cache_list.begin(), cache_list, it) 把 it 指向的节点挪到开头，比 erase+push_front 更高效、更安全（不触发内存分配）
• put() 里若 key 已存在，只更新 value 并调用上述 splice，不要 erase 再 insert，否则 map 迭代器会 dangling
• 超容检查必须放在 put 插入新节点之后做，否则可能误删刚插入的节点

示例片段：

auto it = cache_map.find(key); if (it != cache_map.end()) {     cache_list.splice(cache_list.begin(), cache_list, it->second);     it->second->second = value; // 更新 value     return; } cache_list.emplace_front(key, value); cache_map[key] = cache_list.begin(); if (cache_map.size() > capacity) {     auto last = --cache_list.end();     cache_map.erase(last->first);     cache_list.pop_back(); }

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

很多实现忽略这个边界，结果 capacity == 0 时还往 list 里塞节点，map 不断增长，缓存完全失效。这不是理论问题——实际配置可能读错环境变量或 json，默认值没校验。

立即学习“C++免费学习笔记（深入）”；

• 构造时对 capacity 做非正数检查，capacity 应设为 0，并在 <code>put() 开头直接 return
• 设为 0 后，get() 永远 miss，put() 不存任何东西，符合“零缓存”语义
• 别用 size_t 当参数类型来规避负数——用户传 -1 会被转成极大正数，更危险

为什么不用 std::deque 替代 list？

看起来 deque 支持随机访问、内存更紧凑，但它的迭代器在插入/删除非首尾位置时可能失效（标准未保证稳定），而 LRU 必须频繁在中间 erase + 移到头部，一旦迭代器失效，unordered_map 里存的就成野指针。

• list::iterator 是唯一能保证「插入/删除任意位置都不失效」的序列容器迭代器
• deque 的 erase() 可能使其他迭代器 invalid，c++ 标准明确写了 “pointers and references to the erased elements are invalidated”，map 里存的 iterator 就挂了
• 空间开销不是关键瓶颈，LRU 本就不该存海量项；稳定性压倒局部性能

真要优化内存，可以换用自定义 arena 分配器，但那是另一层复杂度了。