C++如何实现LRU缓存算法-C++-PHP中文网

c++oding="utf-8" ?>

不能只用std::map或std::unordered_map，因为lru需同时支持o(1)查找和按访问序淘汰，须结合哈希表（存key→链表迭代器）与双向链表（维护访问序），并用splice安全移动节点。

c++如何实现lru缓存算法

因为 LRU（Least Recently Used）要求「访问/插入时更新顺序」+「淘汰最久未用项」，而纯哈希表或红黑树不维护访问时间序。你得把「快速查找」和「有序淘汰」两个能力合起来——前者靠哈希，后者靠双向链表（或类似结构）。常见错误是只存键值对，却没记录谁最近被用过，结果一删就乱。

实操建议：

用 std::unordered_map 存 key → iterator（指向链表节点），保证 O(1) 查找
用 std::list 存 std::pair<int int></int>（key, value），利用其 splice 和 begin() 实现 O(1) 移动到头部
每次 get 或 put 时，把对应节点移到链表头；容量超限时，删链表尾

直接 erase 再 push_front 看似可行，但会触发内存分配和拷贝——std::pair 可能含非 trivial 类型，且破坏了原节点地址稳定性。而 splice 是纯指针操作，O(1) 且不重构造。

示例片段（移动已有节点到头部）：

cache_list.splice(cache_list.begin(), cache_list, map[key]);

注意：map[key] 必须是迭代器类型（std::list<...>::iterator</...>），不是值；否则编译不过。

C++ Code Review Master

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

下载

std::list::size() 在 C++11 后是 O(1)，但某些老标准库实现（如早期 libstdc++）仍是 O(n)。更稳妥做法是自己维护一个 int size_ 计数器，在每次 put 插入/删除时增减。

使用场景差异：

如果目标平台明确支持 C++11 且用较新 STL（如 libc++、MSVC 2015+），可放心用 cache_list.size() > capacity_
若需兼容嵌入式或旧环境，手动计数更可靠
别在 get 里做容量判断——LRU 不因读操作扩容或缩容

这是高频 bug。比如先 put(1, 1)，再 put(1, 2)，应视为「更新 value + 提升访问序」，而非「删旧插新」。若误用 erase 再插入，会导致链表节点二次析构或迭代器失效。

正确处理逻辑：

复杂点在于节点更新和链表位置调整必须原子——稍不注意就会让 map 里存着已失效的迭代器。所以所有链表操作后，务必确保 map 中的迭代器仍有效。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！

C++如何实现LRU缓存算法