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

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

用 std::list 搭配 std::unordered_map 来实现一个时间复杂度为 O(1) 的 LRU 缓存，思路听起来很直接，对吧？但这里头有个“魔鬼细节”，直接决定了你的代码是稳定可靠，还是暗藏崩溃风险——那就是对迭代器生命周期的严格控制。

为什么不能先删 map 再删 list？

问题的根源在于，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 更安全

在更新缓存（将某个节点移到链表头部）时，一个常见的误区是手动调用 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()），腾出空间。
• 最后，再插入新节点。这样可以保证在任何时刻，缓存的大小都不会超过预设的容量。

智能指针不是必须的，但 raw pointer 要小心析构

为了追求极致的性能，有些实现会选择使用裸指针（例如 DNodeList*）配合手动 new/delete。这条路当然可行，但你必须成为内存管理的“完美主义者”：

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

当然，使用 std::shared_ptr 和 std::weak_ptr 可以自动管理生命周期，省去很多心智负担，但会引入引用计数的开销。对于追求极限性能的高频缓存场景，手动管理所有权的裸指针方案仍然是主流选择。

最后，再强调一个最容易被忽略，但后果极其严重的点：std::list 的迭代器在节点被 erase() 后立即失效。哪怕你只是把它传给 std::cout << *it 想打印一下看看，这都已经构成了未定义行为。这不是“偶尔会出错”的 bug，而是 C++ 语言标准明确定义的“悬垂访问”，是必须从根源上杜绝的编程错误。