不能只用 std::unordered_map 因为它不维护访问顺序，无法在 O(1) 内更新最近使用或删除最久未用节点；LRU 需双向链表显式维护时序，配合 unordered_map 存迭代器实现 O(1) 查找与更新。
为什么不能只用 std::unordered_map
因为哈希表本身不维护访问顺序，std::unordered_map 查得快（O(1)），但没法在 O(1) 时间内把最近访问的节点提到最前面，也没法快速删掉最久未用的节点。LRU 的“最近/最久”依赖的是时序，必须靠链表结构来显式维护——而单向链表删除尾节点是 O(n)，所以得用双向链表。
std::list 和 std::unordered_map 怎么配对用
核心是让两者指向同一份数据，避免拷贝和同步问题：
-
std::list存完整键值对（比如std::pair<int int></int>），保证节点顺序可变、增删 O(1) -
std::unordered_map的 value 存std::list<...>::iterator</...>，这样查 key 时能立刻定位到链表中对应节点 - 每次
get()或put()后，先用迭代器从 list 中erase()原位置，再push_front()到头部——这步才是“更新最近使用” - 注意：
std::list迭代器不会因插入/删除失效（只要不是它自己被删），所以 map 里存的 iterator 在大部分操作后仍有效
容易崩的几个边界点
面试时一写就错的地方，往往不在主逻辑，而在细节：
- 构造函数里没初始化
capacity，或者忘了检查capacity 的非法输入 -
put()时 key 已存在：要更新 value 并移动到头部，**不能直接 insert 新节点**，否则内存泄漏+map 指向旧迭代器 - 缓存满时删 tail：别用
--cache.end()取最后一个元素，应该用cache.back()；删完记得从 map 中erase()对应的 key - 所有涉及
list::erase(iterator)的地方，确保 iterator 有效——特别是从 map 查不到 key 时，别拿空迭代器去 erase
要不要手写双向链表
LeetCode 和大多数面试场景下，用 std::list 完全合规，且更安全。手写链表只在两种情况有必要：
立即学习“C++免费学习笔记（深入）”；
- 题目明确要求“不使用内置链表类”
- 你需要精细控制内存布局（比如避免
std::list节点分散分配带来的 cache 不友好）
但手写意味着要自己管理 next/prev 指针、处理空指针、保证 erase 不崩溃——实际工程中极少这么干，面试里除非被追问底层实现，否则优先用标准容器。
真正难的不是结构，是怎么在每次操作里严格维持 map 和 list 的一致性：一个节点在 list 里，map 就必须有对应项；删了 list 节点，map 里那条记录也得立刻消失。漏掉一次，后续所有 get() 都可能解引用野迭代器。
