不能只用 std::map 或 std::unordered_map 实现 LRU，因其均不维护访问顺序；需组合 std::unordered_map（O(1) 查找）与 std::list（O(1) 移动/删除），哈希表中存储 value 和 list 迭代器以支持快速定位与更新。
为什么不能只用 std::map 或 std::unordered_map 实现 LRU？
因为 LRU 的核心是「访问顺序」——最近使用的要排在最前，淘汰时踢掉最久未用的。而 std::map 是按 key 排序的，std::unordered_map 根本不维护访问顺序。单靠哈希表或红黑树无法 O(1) 完成「把某节点移到头部」和「删除尾部节点」这两个关键操作。
所以必须组合：用哈希表实现 O(1) 查找，用双向链表（手动管理或借助 std::list）维护访问时序。
-
std::list是双向链表，支持splice()和erase()，但注意：它的迭代器在元素被erase()后失效，因此不能只存迭代器而不更新哈希表中的引用 - 若手写双向链表，需自己管理
next/prev指针，避免内存泄漏；面试中更推荐用std::list+std::unordered_map组合，简洁且不易出错 - 不要用
std::vector模拟链表——移动元素是 O(n)，违背 LRU 的设计目标
如何用 std::list + std::unordered_map 实现 O(1) get / put？
关键在于哈希表中不只存 value，还要存对应在 std::list 中的迭代器，这样每次 get 时能直接用迭代器把节点挪到链表头（O(1)），put 时也能快速定位并更新或删除旧节点。
示例核心逻辑：
立即学习“C++免费学习笔记（深入）”；
class LRUCache {
int capacity_;
std::list> cache_; // {key, value}
std::unordered_map>::iterator> map_;
public:
LRUCache(int capacity) : capacity_(capacity) {}
int get(int key) {
auto it = map_.find(key);
if (it == map_.end()) return -1;
// 把对应节点移到链表头部
cache_.splice(cache_.begin(), cache_, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = map_.find(key);
if (it != map_.end()) {
// 已存在：更新 value 并移到头部
it->second->second = value;
cache_.splice(cache_.begin(), cache_, it->second);
} else {
// 不存在：插入新节点到头部
cache_.emplace_front(key, value);
map_[key] = cache_.begin();
// 检查容量
if (cache_.size() > capacity_) {
int tail_key = cache_.back().first;
cache_.pop_back();
map_.erase(tail_key);
}
}
}
};
-
splice(cache_.begin(), cache_, it->second)是关键：把已有节点高效地“剪切粘贴”到开头，不触发拷贝或构造 - 务必在
put中先处理已存在 key 的情况，再统一处理容量超限——否则可能误删刚插入的新节点 - 注意
std::list::iterator在pop_back()或erase()后失效，但这里只在删除后才从 map 中 erase 对应 key，安全
面试常踩的坑：线程安全、构造函数初始化、边界 case
面试官很少要求线程安全，但如果你主动加 std::mutex，反而容易暴露对锁粒度理解不足——比如整个 get/put 都 lock，性能差；细粒度锁又易死锁。除非明确要求，否则默认单线程实现即可。
- 构造函数里没初始化
capacity_或初始化为负数 → 运行时行为未定义，建议加断言：assert(capacity > 0); -
get(-1)、put(0, 0)等边界输入必须支持，std::unordered_map和std::list对负数 key 完全友好 - 多次
put相同 key 时，不能只更新 map 中的 value 而忘记把 list 中对应节点移到头部——这是最常漏写的逻辑 - 不要在
get中返回引用（如it->second->second的引用），因为外部可能修改它，破坏封装性；返回值即可
如果不用 std::list，手写双向链表要注意什么？
手写链表在面试中属于“展示底层理解”的加分项，但风险也高。重点不是代码多酷，而是别崩：
- 每个节点必须含
key字段：因为淘汰尾部节点时，需要知道该删哪个 key，从而从哈希表中同步清除 - 头尾哨兵节点（dummy head/tail）强烈推荐，省去大量空指针判断，尤其在
splice类操作中逻辑更干净 - 所有 new 出来的节点，必须在
put覆盖或~LRUCache()中 delete，否则面试官会追问内存泄漏问题 - 不要用裸指针管理节点生命周期；C++11+ 更稳妥的做法是用
std::unique_ptr，但注意std::unordered_map中不能存unique_ptr的迭代器——所以还是推荐原生指针 + 手动清理，更贴近真实面试场景
真正难的不是写出代码，是在 get 和 put 的十几行里，不漏掉「更新顺序」「同步哈希表」「检查容量」「处理重复 key」这四个动作的任意一环。
