不能只用 std::unordered_map 实现 LRU，因其不维护访问顺序，无法 O(1) 定位最久未使用项；需哈希表（存 key→list iterator）+ 双向链表（如 std::list）协同实现 O(1) 访问、移动与淘汰。
为什么不能只用 std::unordered_map 实现 LRU？
因为哈希表本身不维护访问顺序，std::unordered_map 查找是 O(1)，但没法在 O(1) 时间内定位“最久未使用”的节点。LRU 的核心诉求是：每次 get 或 put 都要将对应项移到“最近使用”端，同时淘汰时能立刻拿到“最久未使用”端的节点——这必须靠双向链表的头尾快速操作能力。
常见错误是试图用 std::map（按 key 排序）或给哈希表加时间戳字段再遍历找最小值，这两种都退化成 O(n) 淘汰，直接挂面试。
- 哈希表负责 O(1) 定位节点（存的是
key → list iterator） - 双向链表负责 O(1) 移动和裁剪（用
std::list或手写链表均可，推荐std::list避免内存管理风险） - 所有
get和put中涉及的链表操作，必须同步更新哈希表里的迭代器，否则后续erase会崩溃
std::list 迭代器失效问题怎么避坑？
std::list 的迭代器只有在对应节点被 erase 时才失效，插入、移动（如 splice）、遍历都不影响其他迭代器有效性——这是它比 std::vector 或 std::deque 更适合 LRU 的关键。
但要注意：如果你用 list.push_front() + list.erase(it) 再重新 push_front() 来“更新位置”，会产生两次构造/析构，且容易因忘记更新哈希表中保存的旧迭代器而悬垂。
立即学习“C++免费学习笔记（深入）”；
- 正确做法：用
list.splice(list.begin(), list, it)，把已有节点直接挪到开头，不触发元素拷贝，迭代器it依然有效 - 哈希表里存的
std::list必须在每次>::iterator splice后保持可用，无需重赋值 - 如果手写链表，务必确保
next/prev指针在移动时被正确重连，漏掉一个就导致内存泄漏或访问非法地址
put 操作中容量超限的处理顺序为什么不能颠倒？
典型错误写法：先插入新节点到链表和哈希表，再判断是否超限，超了就删尾部——这会导致刚插入的新节点可能立刻被删掉，逻辑错乱。
正确顺序必须是：先检查当前 size 是否已达 capacity，若是，先从链表尾部 pop_back() 并从哈希表中 erase 对应 key；之后再插入新节点。
- 注意
list.back().first是待删节点的 key，必须先取出来再pop_back()，否则节点没了就拿不到 key 去清理哈希表 - 如果
capacity == 0，需特殊处理：所有put都应直接丢弃，且不触发任何链表/哈希操作（否则可能 crash） - 面试官常追问：如果
put的 key 已存在，是否算一次“使用”？答案是肯定的——要先get值，再erase旧节点，再push_front新节点（或用splice），最后更新 value
用 std::list 存 std::pair 还是自定义结构体？
存 std::pair 看似简洁，但可读性差、扩展性弱。比如后续想加访问时间戳、引用计数或锁字段，就得重构。面试中写出带名字段的结构体，会显得更工程化。
但注意：结构体必须支持默认构造、拷贝/移动，且不要在内部做复杂初始化（比如 new 内存），否则 list.splice 可能意外触发析构。
- 推荐定义：
struct CacheNode { int key; int value; CacheNode(int k, int v) : key(k), value(v) {} }; - 哈希表类型应为：
std::unordered_map::iterator> - 避免用
std::list<:unique_ptr>>：智能指针增加间接层，splice虽仍有效，但没必要，且易引发所有权混淆
真正容易被忽略的是异常安全：如果 new 节点失败（虽罕见），或哈希表 insert 抛异常，已做的链表操作必须回滚。实际面试实现可暂不处理，但得知道 std::list::splice 是无抛异常保证（noexcept），而 unordered_map::insert 在 C++17 后也是 noexcept 当 hasher 和 key_equal 不抛时——这点很少有人提，但一问就露馅。
