不能只用 std::unordered_map 实现 O(1) LRU，因其不维护访问顺序，淘汰最久未用元素需遍历，退化为 O(N)；必须结合哈希表（定位）与双向链表（时序），且哈希表须存储 list 迭代器以支持 O(1) 移动。
为什么不能只用 std::unordered_map 实现 O(1) LRU？
因为 std::unordered_map 本身不维护访问顺序，查完一个 key 后无法自动把它“挪到最近使用位置”。单纯靠哈希表，淘汰时只能遍历全部元素找最久未用的，退化成 O(N)。真正的 O(1) LRU 必须把「查找」和「时序更新」解耦：哈希表负责快速定位节点，双向链表负责按访问顺序组织节点。
std::list 能直接当 LRU 链表用吗？
不能直接用 —— std::list 的迭代器在插入/删除时不会失效，但它的 splice 或 erase 操作需要已知迭代器。而哈希表里存的是值（比如 int），不是迭代器。所以必须让哈希表存储指向链表节点的迭代器，即 std::unordered_map。常见错误是存指针或索引，导致链表重排后迭代器失效或越界。
实操建议：
- 定义
Node为std::pair，避免额外结构体开销 - 每次
get()时：先用哈希表查到对应std::list::iterator，再用list.splice(list.begin(), list, it)把该节点移到头部（最近使用） - 每次
put()时：若 key 已存在，同样 splice 到头；若不存在且 size 达上限，先list.pop_back()，再从哈希表 erase 对应 key
哈希表 + std::list 组合的性能陷阱
看似 O(1)，但实际有隐含成本：
-
std::list是非连续内存，频繁splice会放大 cache miss，尤其在大数据量下比自定义静态数组链表慢 2–3 倍 -
std::unordered_map的 rehash 可能触发全表迭代器失效 —— 但注意：std::list迭代器不受影响，只要你不把迭代器存进 map 之前 map 发生 rehash（即先 insert 再取 iterator） - 如果 key 是字符串，
std::hash<:string>在 C++11 中是递归哈希，短字符串也需遍历，可考虑用std::string_view+ 自定义轻量哈希函数
完整类骨架中必须处理的边界
LRU 不是写完 get/put 就完事，这些点漏掉就崩：
-
capacity == 0时，所有put应直接 return，get直接 return -1，否则list.pop_back()会 UB - 重复
put同一个 key 时，不仅要更新 value，还要更新链表位置 —— 容易只改了哈希表值，忘了splice - 用
list.size()判断容量超限？别 ——size()在某些 STL 实现里是 O(N)，应自己维护int _size - 拷贝构造/移动语义没实现？缓存对象被传入 lambda 或容器时可能浅拷贝链表迭代器，导致后续
erase失效
真正难的不是算法逻辑，而是让哈希表里的迭代器始终指向当前有效的链表节点 —— 这个一致性必须靠每一步增删改都同步维护，少一次 erase 或多一次 splice 都会静默崩溃。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
