C++ LRU Cache缓存淘汰算法怎么用list和unordered

必须组合使用 std::list 和 std::unordered_map：list 维护访问时序并支持 o(1) 头尾操作，unordered_map 实现 o(1) key 定位；map 的 value 类型须为 list 迭代器以避免失效，splice 用于移动节点而非 erase+push_front 防止拷贝开销。

c++ lru cache缓存淘汰算法怎么用list和unordered_map实现

为什么不能只用 `std::list` 或只用 `std::unordered_map`

单独用 std::list 无法在 O(1) 时间定位某个 key 对应的节点（得遍历），而单独用 std::unordered_map 无法维护访问时序——淘汰时不知道哪个是最久未用的。所以必须组合：用 unordered_map 存 key → 迭代器映射，用 list 存 {key, value} 并天然支持头尾快速插入/删除。

`list` 节点该存什么、`unordered_map` 的 value 类型怎么设

关键点在于 unordered_map 的 value 必须是 std::list<:pair int>>::iterator</:pair>，这样才能通过 key 直接拿到 list 中对应节点的迭代器，进而做 splice 或 erase。

常见错误是存索引或指针——list 迭代器在插入/删除时不会失效（只要不删它自己），但指针或下标会因内存重分配彻底失效。

示例声明：

std::list<:pair int>> cache_list;
std::unordered_map<int std::list int>>::iterator> cache_map;
</int></:pair>

get 和 put 操作中如何用 `splice` 避免拷贝和重新插入

splice 是核心技巧：把已有节点从 list 中“剪切”到头部（表示最新访问），而不是 erase + push_front —— 后者会触发 pair 构造/析构，且对复杂 value 类型有额外开销。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

正确做法：

get(key) 命中时：用 cache_list.splice(cache_list.begin(), cache_list, cache_map[key])
put(key, value) 已存在时：先更新 cache_map[key]->second = value，再 splice 到头
put 新 key 且超容时：先 cache_list.pop_back()，再用 back 的 key 清掉 cache_map 中对应项

注意：splice 第一个参数是目标位置（begin），第二个是源容器（这里是自身），第三个是待移动的迭代器——顺序错会导致编译失败或逻辑错。

容量边界、重复 key 处理和迭代器失效风险

容易被忽略的细节：

构造时容量为 0？直接拒绝所有操作，或按题意返回默认值（如 get 返回 -1）
put 同一个 key 多次：不是新增节点，而是更新 value + 移动时序；必须先查 map 是否存在，避免误删旧节点
调用 cache_list.erase(it) 后，对应 cache_map 中的迭代器立即失效——所以必须先用 key 查 map，再删 list，最后 erase map 中的 key
list::end() 是无效迭代器，不能解引用；back() 前务必检查 empty()