c++oding="utf-8" ?>
因为LRU需均摊O(1)完成查键、移首、删尾，std::map的O(log n)不满足；unordered_map查键平均O(1)，list::splice移动节点O(1)，且list必须存pair以支持淘汰时从map中精准删除对应key。
为什么不用 std::map 而用 unordered_map + list
因为 std::map 是红黑树，find 和 erase 都是 O(log n)，而 LRU 的核心操作（查键、移至头部、淘汰尾部）必须在均摊 O(1) 完成。用 unordered_map 存键到 list 迭代器的映射，再用 list 维护访问时序，才能逼近理论最优——unordered_map::find 平均 O(1)，list::splice 移动节点也是 O(1)。
注意：不能用 vector 或 deque 替代 list，因为它们不支持 O(1) 的任意位置迭代器删除和移动；也不能只用 unordered_map 加时间戳字段模拟，那样每次 get 都要遍历找最久未用项，退化为 O(n)。
list 里到底存什么？为什么必须存 pair 而不是只存 value
list 必须存完整的 key-value 对（即 pair），否则在淘汰尾部节点时，你无法知道该删掉 unordered_map 中哪个 key —— list::back() 只能拿到 value，没有 key 就没法从哈希表里 erase 对应条目，导致内存泄漏和逻辑错误。
实操建议：
- 定义
list，不要拆成两个容器分别存 key 和 value> cache_list -
unordered_map的 value 类型必须是>::iterator> cache_map list::iterator，不是int*或索引 - 插入新节点后，立即将其迭代器存入 map，避免后续
cache_list.begin()等临时值失效
get 操作中 splice 的正确写法与常见误用
很多人写 cache_list.splice(cache_list.begin(), cache_list, it)，看似把节点移到开头，但这是错的：如果 it 已经是 begin()，splice 行为未定义（libstdc++ 可能 crash，MSVC 可能静默失败）。必须先判断是否已在头部。
正确做法是：
- 查 map 得到迭代器
it - 若
it != cache_list.begin()，才调用cache_list.splice(cache_list.begin(), cache_list, it) - 然后返回
it->second（注意：spliced 后it仍有效，指向新位置）
别用 push_front + erase 组合替代 splice：那会构造新节点、销毁旧节点，多一次内存分配且破坏指针稳定性。
容量限制触发淘汰时，pop_back 和 erase 的顺序不能颠倒
淘汰逻辑必须严格按「先删 list 尾，再根据尾部 key 删 map」的顺序。反过来（先删 map 再删 list）会导致：你拿到的尾部 key 已无效，cache_list.back().first 取出的是悬垂值，或更糟——cache_list 为空时调用 back() 是未定义行为。
安全写法：
- 检查
cache_list.size() > capacity（注意：capacity 是构造时传入的上限，不是cache_list.size()） - 取
auto& tail = cache_list.back()，立刻拿到 key：int key_to_erase = tail.first - 调用
cache_list.pop_back() - 再调用
cache_map.erase(key_to_erase)
边界情况容易被忽略：构造时 capacity == 0，此时所有 put 都应直接丢弃，连 list 插入都跳过；还有多线程场景下必须加锁，但标准题解通常不考虑这点。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
