C++实现基于哈希表的LRU淘汰算法 | O(1)时间复杂度查找与更新【完整源码】
使用 std::list 结合 std::unordered_map 构建时间复杂度为 O(1) 的 LRU 缓存，看似思路清晰，实则暗藏关键细节。其中，对迭代器生命周期的精准控制，直接决定了代码的健壮性与潜在风险。
为何必须先操作链表再操作哈希表？
核心问题在于，std::unordered_map 中存储的是指向链表节点的迭代器（std::list）。一旦对链表执行 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++ 语言标准明确定义的“悬垂访问”，必须从根源上避免。
