不能直接用std::list+unordered_map做LRU，因erase会使map中存储的迭代器失效导致悬垂指针；正确做法是用splice移动节点、同步更新map迭代器，并确保Node含key以支持O(1)淘汰。
为什么不能直接用 std::list 配合 unordered_map 做 LRU？
能，但容易在 erase 和 splice 时出错——std::list::erase(iterator) 会令所有指向被删节点的迭代器失效，而 unordered_map 存的正是这些迭代器。一旦缓存命中后把节点移到链表头，再顺手 erase 原位置，map 里存的迭代器就变成悬垂指针，后续 ++it 或解引用直接 UB。
正确做法是：用 std::list 的 splice 把节点“挪”到头部，不销毁、不重建节点，原迭代器依然有效。同时 map 中只存 list::iterator，不存地址或索引。
-
splice是 O(1)，比erase + push_front更安全且高效 - map 的 value 类型必须是
std::list，不是::iterator Node* - 插入新节点时，先
push_front，再用begin()获取迭代器存入 map
Node 结构体要不要存 key？
要。因为淘汰尾部节点时，得从链表节点反查 key，才能同步删掉 unordered_map 里的条目。如果 Node 只存 value，淘汰时就无法知道该删 map 中哪个 key。
常见错误是只存 value，然后靠 map 的 key 集合去遍历找——这完全违背 O(1) 设计初衷，也根本不可行（map 不提供反向索引）。
-
Node至少含key和value两个字段 - 类型建议用
std::pair或自定义结构体，避免裸指针管理 - 若 key 是 string 或自定义类型，注意移动语义：用
std::move(key)构造 node，减少拷贝
如何安全处理容量超限？
不是每次 put 都检查 size，而是在插入新节点后、更新 map 前，判断 list 大小是否超过 capacity。此时链表尾部节点就是最久未用的，直接取 --list.end() 得到尾迭代器，读出其 key，再删 map 和 list。
关键点在于顺序：必须先删 map（靠 key），再删 list（靠迭代器），否则删完 list 后节点析构，key 可能已不可访问（尤其当 key 是小字符串优化以外的类型）。
- 删 list 用
pop_back()，不是erase(--list.end())——后者需两次解引用，且 end() 是 past-the-end，-- 操作依赖双向迭代器保证安全 - 删 map 用
erase(node.key)，不是erase(it_from_list)——map 的 erase 不接受 list 迭代器 - 容量为 0 时需特殊处理：禁止插入，或直接清空，避免无限循环或断言失败
为什么不用 std::deque 或 std::vector 替代 list？
deque 支持 O(1) 头尾操作，但不支持任意位置的 O(1) 移动；vector 的 insert/erase 中间位置是 O(n)。LRU 的核心操作是「把任意中间节点提到头部」，只有双向链表（std::list）能靠 splice 实现真·O(1) 定位+移动。
有人试过用 vector + index mapping，结果每次命中都要 erase 中间元素并 push_back，实际性能反而更差，还破坏了 cache locality 的假象。
-
std::list迭代器稳定，不因其他节点增删而失效（这是 map 能长期持有它的前提） - 内存开销确实比 vector 大（额外两个指针），但 LRU 本就不适合存海量小对象；权衡的是操作复杂度，不是单字节占用
- 不要手动写链表——
std::list的 splice、merge 等接口已足够健壮，重复造轮子极易引入内存泄漏或迭代器越界
真正难的不是结构拼接，而是迭代器生命周期和删除顺序的配合。哪怕只漏掉一次 map.erase，缓存就可能静默腐化——它不会 crash，但会返回旧值或找不到 key。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
