std::list + std::unordered_map 是实现 O(1) LRU Cache 最常用且靠谱的组合，因 list 支持常数时间节点移动与删除，unordered_map 提供平均 O(1) 查找，二者互补；splice 避免拷贝，map 存迭代器确保定位高效。
用 std::list + std::unordered_map 是最常用且靠谱的组合
LRU Cache 的核心诉求是：O(1) 查找、O(1) 删除任意节点、O(1) 将节点移到头部（即“最近使用”）。std::list 支持常数时间的节点移动和删除（只要拿到迭代器），而 std::unordered_map 提供 O(1) 平均查找，二者配合刚好补足对方短板。
别用 std::vector 或 std::deque 模拟链表——删除中间元素是 O(n)；也别只用 std::map（红黑树）——它按 key 排序，不支持按访问顺序维护，且插入/删除不是真 O(1)。
实操建议：
-
std::list存储std::pair（key-value），每次 get/put 都把对应节点splice到 list 开头 -
std::unordered_map保存 key → list 中对应节点的迭代器，这是 O(1) 定位的关键>::iterator> - put 时若容量超限，直接取
list.back()删除，并从 map 中 erase 其 key
为什么不用 std::map> 加时间戳模拟 LRU
有人想用 std::map 按访问时间戳排序，每次 get 都更新时间戳再重新 insert。这看似可行，但实际踩坑严重：
- 每次 get 都要 erase + insert，至少两次 O(log n) 操作，不是 O(1)
- 时间戳可能重复（尤其高并发或快速调用），导致排序错乱或覆盖
- 无法真正“移动”节点，只能靠重建排序，cache 命中率逻辑易出错
- 标准库没提供“按访问顺序自动重排”的关联容器，硬凑会放大复杂度
std::list::splice 是关键操作，别用 push_front + erase
错误做法：找到节点后 erase 它，再用 value 新建 pair push_front。这会触发额外内存分配和拷贝，且破坏了 map 中保存的原迭代器有效性。
正确做法是用 splice：
cache_list.splice(cache_list.begin(), cache_list, it_in_list);
它只是调整指针，不构造/析构节点，也不影响其他迭代器。注意：splice 第三个参数是迭代器（不是值），所以 map 必须存的是 list::iterator，不是 key 或 index。
注意迭代器失效和线程安全这两个隐形炸弹
单线程下 std::list 的 splice 和 erase 不会使其他迭代器失效，但 std::unordered_map 在 rehash 时所有迭代器可能失效——所以 map 的迭代器不能长期缓存，必须每次通过 key 查找获取。
多线程场景下，即使用了正确的容器组合，get 和 put 仍需加锁（比如 std::shared_mutex 读写锁），否则 map.find + list.splice + map.erase 这几步不是原子的。别幻想无锁实现——除非你用 hazard pointer 等高级机制，那已超出 LRU 本身范畴。
真正容易被忽略的是：当 value 类型较大时，std::pair 这类成员的移动语义是否启用，会影响 splice 后的性能表现。确认你的编译器和 STL 实现对 move-aware 类型做了优化，否则拷贝开销会悄悄吃掉 O(1) 的优势。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
