C++ 怎么实现LRU算法 C++链表结合哈希表设计思路【面试题】

必须配合使用 std::list 和 std::unordered_map：哈希表存迭代器以 O(1) 定位，链表用 splice 维护访问序；淘汰时先取尾 key 再删 map 和 list，构造函数需校验 capacity > 0。

为什么不能只用 std::list 或只用 std::unordered_map

单独用 std::list 查找 key 是 O(n)，不满足 LRU 的 O(1) 查找+更新要求；只用 std::unordered_map 又无法维护访问顺序。必须两者配合：哈希表负责快速定位节点，双向链表负责按访问序维护位置。

关键点在于——哈希表的 value 不能存原始数据，而要存指向链表节点的迭代器（std::list<:pair v>>::iterator）。这样在 get 时查哈希得迭代器，再用迭代器在 list 中做 splice 操作，全程 O(1)。

常见错误是试图用指针或自定义结构体模拟节点，结果手动管理内存出错；或者把 std::list 当成普通容器反复 erase+push_front，导致迭代器失效（std::list 的迭代器只有被显式 erase 才失效，但频繁插入删除仍易误用）。

std::list 迭代器作为 value 的实际写法

声明哈希表时，value 类型必须匹配 list 的迭代器类型：

立即学习“C++免费学习笔记（深入）”；

std::unordered_map>::iterator> cache_map;

插入新节点时，先 push_front 到 list，再用 begin() 获取刚插入的迭代器存入 map：

• cache_list.push_front({key, value});
• cache_map[key] = cache_list.begin();

get 操作中，查到迭代器后直接 splice 到开头（不是 erase + push_front）：

cache_list.splice(cache_list.begin(), cache_list, it);

splice 是安全的，它移动节点而不拷贝、不使其他迭代器失效，是 std::list 提供的专用于此类场景的 O(1) 接口。

Munch

AI营销分析工具，长视频中提取出最具吸引力的短片

下载

容量满时淘汰 tail 节点的细节处理

淘汰必须同时清理两个地方：链表尾部节点 + 哈希表中对应 key：

• 从 cache_list.back().first 取出 key
• 调用 cache_map.erase(key)
• 再调用 cache_list.pop_back()

顺序不能反：如果先 pop_back()，就拿不到 key，无法清理 map；如果先 erase map，后续 pop_back 就无法反向验证。另外注意，std::list::back() 要求非空，所以淘汰前必须检查 cache_list.size() > capacity，且初始化时 capacity 应 > 0。

面试常忽略的点：构造函数里 capacity 传 0 怎么办？建议加断言或抛异常，而不是静默接受——LRU 容量为 0 没有意义。

用 std::list 还是手写双向链表

工业代码优先用 std::list：它已保证节点内存布局稳定、迭代器长期有效、splice 安全；手写链表容易在 move/swap/copy 构造时出 bug，且面试中除非明确要求，否则没必要重造轮子。

但要注意：C++11 后 std::list 的迭代器不是原生指针，不能直接解引用后取地址做指针运算；它的 size() 在某些旧标准库实现中是 O(n)，不过现代 libstdc++ 和 libc++ 都是 O(1)。若需绝对确定，可自己维护一个 size 计数器。

真正复杂的地方不在结构，而在边界：put 重复 key 时要更新 value 并移动位置；get 不存在 key 时返回默认值且不改变状态；多线程未加锁——这些才是面试追问重点，而不是“怎么写 splice”。