必须结合 std::list 和 std::unordered_map：前者维护访问顺序并支持 O(1) 头尾操作，后者实现 key 到节点迭代器的 O(1) 查找；list 节点应存 pair<Key,Value>，map 的 value 存对应 iterator，通过 splice 更新顺序，自维护 size 避免 size() 开销。
为什么不能只用 std::list 或只用 std::unordered_map
单独用 std::list 无法在 O(1) 时间定位某个 key 对应的节点（查找需 O(n)）；只用 std::unordered_map 则没法维护访问顺序，删除最久未用项时得遍历全部 value 找“时间戳最小”的——这又退化成 O(n)。LRU 的核心约束是所有操作（get、put）必须平均 O(1)，所以必须两者结合：unordered_map 提供 key → 节点指针的快速跳转，list 提供 O(1) 头尾增删和顺序维护。
list 存什么？unordered_map 的 value 类型怎么设计
推荐把 key 和 value 一起存在 list 的每个节点里（比如 std::pair<int, int>），而不是只存 value。这样 unordered_map 的 value 就能直接存 std::list<...>::iterator，后续通过迭代器可立即拿到 key 和 value，删除时也能顺手从 map 中擦除 key。
关键点：
-
unordered_map的 key 是用户传入的 key（如int），value 是对应 list 节点的迭代器 -
list每个元素是std::pair<const Key, Value>，不能只存 value —— 否则删除节点后无法反查 key 来清理 map - 避免用
list::end()初始化迭代器变量，它不是有效节点；建议用list::iterator{}（空构造）或直接声明后赋值
get 和 put 操作中如何更新 list 顺序
每次 get 或 put 命中已有 key，都要把这个节点移到 list 最前面（表示最近使用）。C++ std::list 不支持“把任意迭代器指向的节点移到开头”这种原地操作，但可以用 splice：
立即学习“C++免费学习笔记（深入）”；
cache_list.splice(cache_list.begin(), cache_list, it); // it 是目标节点迭代器
注意：splice 是 O(1)，且不会使其他迭代器失效，比先 erase 再 push_front 更安全（后者会使原迭代器失效，map 中存的就变 dangling）。
put 时若容量满，要先删 list 尾部节点（--cache_list.end()），再从 map 中 erase 对应的 key。
容易被忽略的边界：key 重复 put、空缓存、类型泛化
面试写代码常漏掉这些：
- 当
put(key, value)的key已存在，不能直接插入新节点，要先用 map 查到旧节点，用splice移动并更新 value - 容量为 0 时，
put应该什么都不做（包括不存 map、不改 list），否则后续操作会出错 - 如果泛化成模板类，
std::list::splice在 C++17 前要求两个 list 类型完全一致（包括分配器），别用自定义分配器增加复杂度 - 不要用
list.size()判断容量超限——它在某些标准库实现中是 O(n)；自己维护一个int size_计数更稳妥
实际调试中最常崩在迭代器失效和尾节点取值上：--cache_list.end() 是合法的，但 cache_list.end()-- 不行；空 list 时这个操作会 UB。
