应使用 unordered_map + list 实现 lru 缓存：unordered_map 提供 o(1) 查找，list 支持 o(1) 节点移动与删除，二者协同维护访问时序；关键在于同步更新、正确管理迭代器、精准控制容量边界。
为什么不用 std::map 而用 unordered_map + list
因为 std::map 自带排序，但 LRU 不需要按 key 排序，只关心访问时序；用 unordered_map 查 key 是 O(1)，而 std::map 是 O(log n)，纯拖慢。但 unordered_map 本身不维护顺序，所以得靠 list 存实际数据节点，并在每次访问时把对应节点移到开头——这就是“最近使用”的物理体现。
常见错误是试图用 unordered_map 存值 + 单独用 vector 记录访问顺序：vector 删除中间元素是 O(n)，一删就破功；list 的 erase(iterator) 才是真正的 O(1)。
- 必须用
list（不是vector或deque），否则移除旧节点或前置新节点无法常数时间完成 -
unordered_map的 value 类型得存list<pair int>>::iterator</pair>，不然找不到要挪的节点 - 别在
list里反复find()——那是 O(n)，直接靠 map 查 iterator 就行
get() 和 put() 怎么联动 list 和 unordered_map
核心就一条：所有对缓存的修改，都必须同步更新两个容器。不是“先改 list 再改 map”，而是“拿到 iterator 后，一步删、一步插、一步更新 map”。
比如 get(key) 命中时：从 unordered_map 拿到对应 list 迭代器 → 用 list.splice() 把那个节点提到开头 → 返回值；没命中就返回 -1，不碰 list。
立即学习“C++免费学习笔记（深入）”；
put(key, value) 更关键：如果 key 已存在，除了更新值，还得把对应节点提到开头；如果不存在且 size 已满，得先删 list 尾部节点（最久未用），再从 unordered_map 里 erase 对应 key。
- 删尾部前，一定先用
back().first取出 key，再去unordered_map.erase()，否则 map 里残留脏指针 - 用
list.splice(list.begin(), list, it)移动节点，比erase + push_front更安全（避免临时构造/析构） - 别在
put()里对已存在 key 调erase再重新insertmap —— 直接改 value 并移动 list 节点就行
迭代器失效是最大暗坑
list 迭代器只有在被 erase() 的节点上才失效，插入/移动不影响其他迭代器；但 unordered_map 在 rehash 时会批量让所有迭代器失效——所以绝不能存 unordered_map::iterator 到 list 里，只能存 list::iterator 到 map 里。
另一个常见翻车点：把 list 节点的引用或指针存进 map。一旦 list 发生 splice 或 erase，引用/指针就悬空。必须存 list::iterator，它是稳定的（只要节点没被删）。
- 声明 map 时写成
unordered_map<int list int>>::iterator></int>，别偷懒 typedef 模糊掉类型 - 每次从 map 取出 iterator 后，立刻检查是否有效（比如加个
if (it == cache_list.end())防御性编程） - 不要在
list上做循环遍历时同时调erase()—— 用remove_if或先收集待删 key
容量边界和构造初始化怎么写才不漏逻辑
capacity 是硬上限，但“当前 size”得自己维护，别依赖 list.size() 做判断——虽然它平均 O(1)，但某些标准库实现是 O(n)，而且你本就不该让它涨到超限再删。
典型错误是在 put() 开头就 if (map.size() >= capacity) 然后删尾，但忘了：如果 key 已存在，这次 put 不增加 size，不该删。
- 正确做法：先查 key 是否存在；存在则只更新 + 移动节点；不存在才判断是否要删尾（即
list.size() == capacity） - 构造函数里别直接
list.resize(capacity)—— list 是空的，resize 出来的是默认构造的 pair，没意义 - 测试时务必覆盖
capacity == 0场景：此时所有put()都该立即丢弃，get()全返回 -1
真正麻烦的从来不是结构选型，而是删节点时 map 和 list 的删除顺序、iterator 的生命周期、以及 capacity 判断时机这三件事咬在一起——错一个，缓存就开始“记得不该记的，忘掉不该忘的”。
