C++实现基于哈希表的LRU淘汰 _ 复杂度O(1)级查找更新【源码】

C++实现基于哈希表的LRU淘汰算法 | O(1)时间复杂度查找与更新【完整源码】

免费影视、动漫、音乐、游戏、小说资源长期稳定更新！ 👉 点此立即查看 👈

使用 std::list 结合 std::unordered_map 构建时间复杂度为 O(1) 的 LRU 缓存，看似思路清晰，实则暗藏关键细节。其中，对迭代器生命周期的精准控制，直接决定了代码的健壮性与潜在风险。

为何必须先操作链表再操作哈希表？

核心问题在于，std::unordered_map 中存储的是指向链表节点的迭代器（std::list>::iterator）。一旦对链表执行 list.erase(it)，该迭代器立即失效。若此时仍通过失效迭代器访问 map[key] 或调用 map.erase(key)，将触发未定义行为：可能导致程序崩溃、返回随机值，或引发内存检测工具（如 ASan）报出 use-after-free 错误。

因此，正确的操作顺序至关重要：

• 首先，从链表尾部获取待淘汰键值：cache.back().first
• 接着，从链表中移除该节点：cache.pop_back()
• 最后，从哈希表中删除对应条目：map.erase(key)

此顺序不可颠倒。

使用 std::list::splice() 实现更安全的节点移动

在更新缓存（将节点移至链表头部）时，常见的错误是手动调用 erase() 后接 push_front()。这种方法不仅效率略低，更易遗漏关键步骤：更新哈希表中对应的迭代器。一旦忘记更新，哈希表将指向已删除的无效位置。

更优雅且安全的方案是采用 std::list::splice()。该方法能在链表内部“剪切”并“粘贴”节点至新位置，整个过程不涉及节点的构造与析构，因此所有指向该节点的迭代器、指针和引用均保持有效，完美契合此场景需求。

典型实现如下：

auto it = map[key];
cache.splice(cache.begin(), cache, it); // it 仍然有效，可直接用于 map[key] = it;

需特别注意：splice() 的第三个参数应为迭代器，而非节点值；且该方法仅适用于同一链表容器内部的节点移动。

容量检查应在插入前完成

容量管理的时机是另一常见陷阱。部分实现会先执行 push_front() 插入新节点，再检查 size() > capacity 并执行淘汰。这种做法会导致缓存出现短暂的“超容”状态。例如，容量设为2时，链表可能瞬间存在3个节点。尽管逻辑上会立即删除一个，但此中间状态在并发环境下可能被其他线程访问，或触发调试断言，带来不必要的复杂性。

更稳健的策略是前置检查：

• 当插入新键时，在插入操作之前，先判断 cache.size() == capacity。
• 若缓存已满，则先执行淘汰流程（pop_back() + map.erase()），释放空间。
• 最后再插入新节点。如此可确保缓存大小始终不超过预设容量。

智能指针与裸指针的内存管理权衡

为追求极致性能，部分实现会选择裸指针（如 DNodeList*）配合手动 new/delete。此方案可行，但要求开发者成为内存管理的“完美主义者”：

• 确保所有代码路径（包括异常分支）均正确释放节点内存。
• 在 LRU 缓存类的析构函数 ~LRU() 中，必须遍历哈希表并 delete 每个存储的指针。
• 切勿依赖 std::list 的自动析构来释放指针——它仅会析构链表节点中存储的 pair 对象，而不会处理 pair 内可能包含的指针。

当然，使用 std::shared_ptr 与 std::weak_ptr 可自动管理生命周期，降低心智负担，但会引入引用计数开销。对于高频缓存场景，手动管理所有权的裸指针方案仍是主流选择。

最后再次强调一个极易忽略但后果严重的细节：std::list 的迭代器在节点被 erase() 后立即失效。即使仅将其传递给 std::cout << *it 进行打印，也已构成未定义行为。这并非“偶发性”错误，而是 C++ 语言标准明确定义的“悬垂访问”，必须从根源上避免。