C++如何实现一个简单的LRU缓存策略-C++-PHP中文网

不能只用 std::map 或 std::unordered_map 实现 lru，因其无法在 o(1) 时间内同时完成查键、更新访问顺序和淘汰最久未用项；必须配合 std::list 与 std::unordered_map，通过存储有效迭代器并用 splice 安全移动节点来保证正确性。

c++如何实现一个简单的lru缓存策略

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

因为 LRU 的核心是“访问即置顶”，需要在 O(1) 时间内完成：① 查键、② 更新访问顺序、③ 淘汰最久未用项。单纯哈希表或红黑树无法 O(1) 移动元素位置，也无法快速定位并删除尾部节点。

常见错误是用 std::list + std::unordered_map 但没同步维护迭代器，导致 erase 时迭代器失效或重复插入；或者用 std::vector 手动移位，结果每次 get 都是 O(N)。

必须让 map 存储指向 list 节点的迭代器，且保证该迭代器在 list 元素移动时仍有效（std::list 迭代器不因插入/删除失效）
list 的每个节点需同时存 key 和 value，否则 map 里只存 value 会导致淘汰时无法反查 key
避免在 put 中先 erase 再 push_front —— 若 key 已存在，应直接更新 value 并移动到头部，而不是删再插

`std::list` + `std::unordered_map` 的正确配对方式

关键不是“用什么容器”，而是“怎么绑定”。map 的 value 类型必须是 std::list<:pair int>>::iterator</:pair>，这样能直接通过 key 定位到 list 中对应节点，再用 splice 把它挪到开头。

示例片段（非完整类，仅示意核心逻辑）：

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

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

// get 操作
auto it = cache_map.find(key);
if (it == cache_map.end()) return -1;
cache_list.splice(cache_list.begin(), cache_list, it->second); // O(1) 移动
return it->second->second;</int></:pair>

splice 是安全移动的关键：它不复制元素，只调整指针，且目标迭代器保持有效
不要用 erase + push_front 替代 splice，前者会触发两次内存操作，且可能使 map 中旧迭代器悬空
insert 新项时，先 cache_list.push_front({key, value})，再把新节点的 begin() 迭代器存入 map —— 注意 push_front 返回 void，得用 cache_list.begin() 获取

容量超限时如何安全淘汰尾部节点

淘汰必须和 map 同步：先从 list 尾部取 key，再用这个 key 去 map 里删对应条目，否则 map 里残留无效迭代器，下次访问会 crash。

典型错误写法：cache_list.pop_back(); —— 这样根本不知道删的是哪个 key，map 里还留着已失效的迭代器。

正确做法：取 cache_list.back().first 得到 key，再调 cache_map.erase(key)，最后 cache_list.pop_back()
顺序不能颠倒：必须先删 map，再删 list；反过来会导致 map 里迭代器指向已销毁节点
如果用 C++11 以上，可借助 auto& back_pair = cache_list.back(); 避免重复取值