用 std::list + std::unordered_map 可实现 O(1) LRU 缓存：unordered_map 提供 key→list 迭代器映射以支持快速查找，list 支持头插、尾删和指定位置删除，共同满足 get/put/淘汰的常数时间要求。
用 std::list + std::unordered_map 实现 O(1) LRU 缓存
LRU 缓存的核心难点是：既要快速查找（get），又要快速移动到最近使用位置（put更新顺序），还要在容量满时删掉最久未用项。C++ 标准库里，std::list 支持常数时间的节点删除和头/尾插入，std::unordered_map 提供 O(1) 的 key 查找 —— 二者组合刚好满足需求。
关键设计点：std::unordered_map 存 key → iterator（指向 std::list 中对应 pair<key, value> 的迭代器），这样 get 时能直接定位并移到链表头部；put 时若已存在，就用迭代器擦除原节点再重新插入头部；若超容，则删掉链表尾部节点，并从 map 中移除对应 key。
注意：std::list::erase(iterator) 是合法且高效的，但不能保存失效迭代器 —— 每次 erase 后原迭代器立即无效，所以必须先用 map[key] 获取、操作、再更新 map。
std::list 节点值类型选 std::pair<int, int> 还是自定义结构体？
用 std::pair<int, int> 最简洁，但可读性差；用结构体（如 struct CacheNode { int key; int val; };）更清晰，尤其当未来要扩展字段（比如访问时间戳、引用计数）时。实际性能无差异 —— std::list 存的是对象副本，两者都是 trivial 类型，移动开销一致。
立即学习“C++免费学习笔记（深入）”；
实操建议：
- 初期用
std::pair<int, int>快速验证逻辑 - 上线前或需维护时，换成命名明确的结构体，避免
it->first/it->second带来的歧义 - 不要用
std::vector或std::deque替代std::list：前者不支持 O(1) 中间删除，后者不保证迭代器在插入/删除后稳定
如何处理 put 时 key 已存在但 value 不同的情况？
LRU 规范要求：put(k, v) 若 k 已存在，应更新 value 并将该节点移到最近使用位置（即链表头），而不是忽略或报错。常见错误是只更新 map 中的 value，却忘了调整 list 顺序 —— 这会导致缓存淘汰逻辑错乱，最久未用项可能不是真实最久的。
正确做法（以 std::pair 为例）：
if (cache_map.find(key) != cache_map.end()) {
auto it = cache_map[key];
cache_list.erase(it); // 先删旧位置
}
cache_list.push_front({key, value});
cache_map[key] = cache_list.begin(); // 更新 map 中的迭代器
注意：push_front 返回新节点的迭代器，必须立刻存入 map；如果先 erase 再 push_front 但没更新 map，后续 get 会解引用已失效迭代器，触发未定义行为。
为什么不用 std::map 替代 std::unordered_map？
std::map 是红黑树，查找/插入/删除都是 O(log n)，而 LRU 要求所有核心操作 O(1)，用它会让整体复杂度退化为 O(log n)，尤其在高并发或大数据量场景下明显拖慢。除非你明确需要 key 有序遍历（LRU 本身不需要），否则没有理由选 std::map。
另一个坑：std::unordered_map 的迭代器在 rehash 时会失效（例如插入导致扩容）。但只要你不保存跨操作的迭代器（即每次 get/put 都现场查 map 取迭代器），就完全安全 —— 因为 cache_map[key] 总返回当前有效迭代器。
补充：C++20 起可考虑 std::unordered_map::extract 避免拷贝，但对 int 这种小类型意义不大；真正受益的是带大成员的对象缓存。
最易被忽略的一点：std::list::iterator 不能序列化或跨线程共享，如果你的缓存要用于多线程环境，必须加锁（如 std::shared_mutex），且锁粒度要覆盖“查 map → 操作 list → 更新 map”整个临界区，不能只锁其中一步。
