C++实现LRU缓存Linit控制 _ 双向链表与哈希映射组合【源码】

先说结论：在C++里实现LRU缓存，最靠谱的方案，还是手写一个双向链表，搭配一个存着节点裸指针的哈希表。直接用std::list替代，看着很美，但实操起来，坑比想象中多。

为什么 std::list 不能直接替代自定义双向链表

理论上，std::list::erase(iterator) 确实是 O(1) 的，问题在于，你得先拿到这个迭代器。而哈希表里存的是值，不是迭代器。想在std::list里通过值反查迭代器，那就得 O(N) 遍历了，这跟LRU的初衷背道而驰。

当然，有人会想到在哈希表里存std::list::iterator，配合splice来移动节点。C++11之后，std::list的迭代器是可拷贝的，这个方案技术上可行。但有个隐含风险：这个迭代器的生命周期，必须和它所指向的节点严格同步。一旦节点被erase，这个迭代器就立刻失效了，后面再拿它操作，就是未定义行为。

所以，更稳妥的做法，就是自己动手搞一个双向链表节点：

• 每个节点包含 key、value、prev、next 四个字段。
• 哈希表用 std::unordered_map，直接存节点的裸指针。
• 所有增删操作，都是指针的重新指向，没有内存重分配，没有迭代器失效的烦恼。

get() 和 put() 中如何避免重复逻辑

写的时候，最怕的就是get()里写一遍“把节点移到头部”，put()里再写一遍，一不留神就漏掉某个指针赋值，尤其是边界情况。

实操建议很直接：把“把某节点移到头部”这个操作，抽成一个独立的函数。比如moveToHead(Node* node)，内部拆成两步：removeNode(node) 和 addToHead(node)。

注意，removeNode() 里必须判空：

• if (node->prev) node->prev->next = node->next;
• 同理处理 node->next。

而在addToHead()里，更新指针的顺序至关重要。得先更新 node->next = head->next，再更新 head->next->prev = node，最后把 head->next 指向node。顺序弄反了，链表就断了。

容量超限时，tail 节点删除的正确顺序

删掉 tail 节点，绝对不是 delete tail 这么简单。它涉及三件事：从哈希表移除 key、从链表解链、释放内存。顺序错了，不是野指针就是内存泄漏。

标准流程，必须严格遵守：

1. 先从 std::unordered_map 里，用 erase(tail->key) 把映射关系摘除。
2. 再调用 removeNode(tail)，把它从链表中摘下来。此时 tail 指针还是有效的，能取到里面的 key。
3. 最后才 delete tail。删完之后，立刻更新 tail 指针指向它的前一个节点，也就是 tail = tail->prev。

千万记住，如果先 delete tail，再去 erase(map[tail->key])，那 tail->key 已经是野指针了，访问它就是未定义行为。

构造函数里初始化 head/tail 哨兵节点的必要性

不用哨兵也能做，但每处插入和删除，都得加一堆判空逻辑：if (!head) { head = node; tail = node; }。代码膨胀不说，还特别容易出错。

引入两个固定哨兵节点（head 和 tail 永远不存真实数据），所有操作就变成了“在中间插入”或“在中间删除”，逻辑高度统一，边界情况全被吸收掉了。

关键细节：

• 构造函数里，初始化 head->next = tail，tail->prev = head，其他字段置空。
• 所有真实数据节点，都插在 head 和 tail 之间。get() 后调用 moveToHead()，完全不用管 head 是否为空。
• 容量检查，直接比对 size_ 和 capacity 就行，不需要遍历链表算长度。

哨兵不是炫技，它是把代码里所有可能出问题的边界 case 全部收归一处，少一个 if，就少一个 bug 滋生的温床。