c++中如何实现LRU缓存淘汰算法_c++ LRU Cache设计思路-C++-PHP中文网

用 std::list + std::unordered_map 可实现 O(1) LRU 缓存：unordered_map 提供 key→list 迭代器映射以支持快速查找，list 支持头插、尾删和指定位置删除，共同满足 get/put/淘汰的常数时间要求。

c++中如何实现lru缓存淘汰算法_c++ lru cache设计思路

用 `std::list` + `std::unordered_map` 实现 O(1) LRU 缓存

LRU 缓存的核心难点是：既要快速查找（get），又要快速移动到最近使用位置（put更新顺序），还要在容量满时删掉最久未用项。C++ 标准库里，std::list 支持常数时间的节点删除和头/尾插入，std::unordered_map 提供 O(1) 的 key 查找 —— 二者组合刚好满足需求。

关键设计点：std::unordered_map 存 key → iterator（指向 std::list 中对应 pair 的迭代器），这样 get 时能直接定位并移到链表头部；put 时若已存在，就用迭代器擦除原节点再重新插入头部；若超容，则删掉链表尾部节点，并从 map 中移除对应 key。

注意：std::list::erase(iterator) 是合法且高效的，但不能保存失效迭代器 —— 每次 erase 后原迭代器立即无效，所以必须先用 map[key] 获取、操作、再更新 map。

`std::list` 节点值类型选 `std::pair` 还是自定义结构体？

用 std::pair 最简洁，但可读性差；用结构体（如 struct CacheNode { int key; int val; };）更清晰，尤其当未来要扩展字段（比如访问时间戳、引用计数）时。实际性能无差异 —— std::list 存的是对象副本，两者都是 trivial 类型，移动开销一致。

实操建议：

初期用 std::pair 快速验证逻辑
上线前或需维护时，换成命名明确的结构体，避免 it->first/it->second 带来的歧义
不要用 std::vector 或 std::deque 替代 std::list：前者不支持 O(1) 中间删除，后者不保证迭代器在插入/删除后稳定

如何处理 `put` 时 key 已存在但 value 不同的情况？

LRU 规范要求：put(k, v) 若 k 已存在，应更新 value 并将该节点移到最近使用位置（即链表头），而不是忽略或报错。常见错误是只更新 map 中的 value，却忘了调整 list 顺序 —— 这会导致缓存淘汰逻辑错乱，最久未用项可能不是真实最久的。

正确做法（以 std::pair 为例）：

logos-node

在 Linux x86_64 上安装、更新或检查 Logos 区块链测试网验证节点。用于用户需要搭建 Logos 节点时使用。

下载

if (cache_map.find(key) != cache_map.end()) {
    auto it = cache_map[key];
    cache_list.erase(it);  // 先删旧位置
}
cache_list.push_front({key, value});
cache_map[key] = cache_list.begin();  // 更新 map 中的迭代器

注意：push_front 返回新节点的迭代器，必须立刻存入 map；如果先 erase 再 push_front 但没更新 map，后续 get 会解引用已失效迭代器，触发未定义行为。