不能只用 std::unordered_map 实现 LRU，因其无法在 O(1) 内移动节点至表头以维护访问顺序；必须结合双向链表（如 std::list）并通过 splice 避免迭代器失效，配合哈希表实现 get/put 均为 O(1)，且需校验 capacity 合法性。
为什么不能只用 std::unordered_map 实现 LRU？
因为哈希表本身不记录访问顺序，std::unordered_map 查找是 O(1)，但无法在常数时间内把某个 key “移到最近使用位置”。LRU 的核心操作——“访问即置顶”和“淘汰最久未用项”，必须支持快速定位 + 快速移动节点。单靠哈希表做不到，必须搭配能 O(1) 插入/删除任意节点的结构，双向链表正好满足。
std::list 能直接用吗？注意迭代器失效问题
可以，但要小心：每次 list::erase(iterator) 后，该迭代器立即失效；而如果你把 list::iterator 存在哈希表里（比如 unordered_map<key list>::iterator></key>），那每次从链表中移除节点后，对应 map 里的 iterator 就成了悬空指针——下次再解引用会崩溃。
实操建议：
- 用
list::splice()把节点从中间“剪切”并“粘贴”到头部，避免 erase + push_front，这样迭代器保持有效 - 或者改用自定义双向链表（含
prev/next指针），自己管理节点生命周期，更可控 - 若坚持用
std::list，务必在每次erase后同步更新 map 中的 iterator，但逻辑易错，不推荐
如何让 get() 和 put() 都做到 O(1)？
关键在于哈希表与链表的双向绑定：
立即学习“C++免费学习笔记（深入）”；
- 哈希表存
key → node*（或list::iterator），提供 O(1) 定位 - 链表节点存
key和value，头部为最近使用，尾部为最久未用 -
get(key)：查哈希表 → 找到节点 → 用splice移到链表头 → 返回 value -
put(key, value)：已存在则更新 value 并 splice 到头；不存在则新建节点插头，若超容，删尾节点并从哈希表 erase 对应 key
示例片段（简化）：
auto it = cache_map.find(key);
if (it != cache_map.end()) {
cache_list.splice(cache_list.begin(), cache_list, it->second); // O(1) 移动
it->second->second = value; // 更新值
} else {
cache_list.emplace_front(key, value);
cache_map[key] = cache_list.begin();
if (cache_list.size() > capacity) {
auto& tail = cache_list.back();
cache_map.erase(tail.first);
cache_list.pop_back();
}
}
容量为 0 或负数时怎么处理？
很多实现忽略这个边界，结果一设 capacity = 0 就无限插入、不淘汰，缓存失控。
正确做法：
- 构造时对
capacity做校验：if (capacity - 在
put()中，先判断capacity == 0：此时所有put都应等效于“清空旧值 + 不缓存新值”，即直接 erase 原 key（如有），且不插入新节点 - 注意：
capacity = 0时get()仍应返回 -1（或默认值），但不触发任何链表操作
这个点容易被跳过，但线上环境一旦配置错误，会导致内存持续增长。
