用 std::list + std::unordered_map 实现 lru 缓存，核心是 list 维护访问顺序、map 提供 o(1) 查找，每次 get/put 需将对应节点 splice 至头部，容量超限时同步删除 list 尾部节点和 map 中对应 key，避免迭代器失效与内存泄漏。
用 std::list + std::unordered_map 实现最简 LRU
LRU 缓存核心是「查得快、删得快、更新顺序快」，C++ 标准库里没有现成的 LRU 容器，但组合 std::list（维护访问顺序）和 std::unordered_map（O(1) 查 key）就能稳稳拿下。
关键不是写得多，而是让两个容器协同不脱节：map 存的是 key → list iterator，每次 get 或 put 都要把对应节点移到 list 开头（或末尾，取决于你定义“最近”在哪边），容量超限时删掉尾部节点。
- 务必用
list::splice移动节点，别erase + push_front—— 后者会析构再构造，如果 value 类型非 trivial（比如含 string、vector），可能意外触发拷贝/移动，且 iterator 失效 -
unordered_map的 value 类型必须是list<pair v>>::iterator</pair>，不是pair<k></k>；否则无法反向定位节点位置 - 初始化时预留 map 容量（
reserve(capacity)），避免 rehash 导致所有迭代器失效（这是深坑，尤其在多线程未加锁时直接崩溃）
为什么不用 std::map 或 std::vector
std::map 按 key 排序，但 LRU 依赖的是访问时间序，不是 key 序；而且它不支持 O(1) 移动节点到头部。std::vector 看似简单，但删除中间元素（比如把某次访问的元素提到 front）是 O(n)，缓存命中高时性能断崖下跌。
- 实测：10 万次 get/put 混合操作，
list+map组合比vector快 8–12 倍（尤其 capacity 较小时） -
std::map的extract（C++17）能搬节点，但不能按访问序重排——你没法告诉它“这个 key 刚被访问了，请挪到逻辑开头” - 若用
deque替代list，看似连续内存更快，但中间删除仍需搬移，且迭代器在push_front/pop_back后可能失效（不符合标准保证）
put 时 key 已存在，怎么避免重复插入
这是最容易写出 bug 的地方：有人先 map.find()，没找到才 list.push_front，但若 key 存在，只更新 value 却忘了把对应节点移到头部，LRU 顺序就乱了。
立即学习“C++免费学习笔记（深入）”；
- 统一走「先删后插」流程：不管 key 是否存在，都先用 iterator 从 list 中
erase（若存在），再push_front新节点 - map 更新要同步：删 list 节点前，先用它的 iterator 反查 key（
it->first），再从 map 中erase对应 key；或者更稳——map 存的是iterator，删 list 时 map 还持有旧 iterator，此时直接map.erase(key)即可 - 注意异常安全：如果
value构造抛异常（比如 string 分配失败），list.push_front尚未执行，但 map 可能已insert了 dangling iterator —— 所以建议先构造好pair，再同时更新 list 和 map
容量满时删 tail 节点，但 map 没清理会怎样
现象很典型：缓存看起来满了，get 返回 nullptr 或默认值，但反复 put 后内存持续上涨，map.size() 远大于 list.size() —— 这是 map 里残留了已从 list 删除节点的 iterator，下次 get 时解引用直接 UB（通常 crash 或读垃圾值）。
- 删 tail 必须两步原子完成：
list.pop_back()→ 立即用尾部原 key 从 map 中erase - 不要依赖 list 节点的
second（value）去反推 key：如果 value 类型重载了operator==且不唯一（比如两个不同 key 对应相同 value），map 删除就会漏掉 - 调试技巧：在
put结束后 assert(map.size() == list.size())，上线前关掉，开发期能立刻揪出不同步问题
真正难的不是写对第一次，而是保证每次 get、put、扩容、异常路径下 list 和 map 的 size、iterator 有效性、key-value 关联始终一致。少一个 erase，就埋一个运行时崩点。
