c++如何实现LRU缓存算法_c++ LRU设计与实现【源码】_网络技术

用std::list+std::unordered_map实现O(1)LRU缓存的关键是：用map映射key到list迭代器，通过splice快速移动节点至头部，淘汰时取back()并同步更新map；需注意splice参数合法性、迭代器有效性、put时的更新/插入逻辑顺序及线程安全限制。

用 `std::list` + `std::unordered_map` 实现 O(1) LRU

LRU 缓存的核心难点是「快速定位最久未用项」和「频繁移动访问项到最近位置」，C++ 标准库里没有现成的双向链表+哈希混合结构，但可以用 std::list 存节点顺序、std::unordered_map 做键到链表迭代器的映射，两者配合达成插入、查询、更新全 O(1)。

关键点在于：不能把值直接存在 std::list 里再靠遍历找——那会退化成 O(n)；必须让 map 的 value 是 std::list::iterator，这样通过 key 一查就知道它在链表哪，splice 一下就能移到头部。

std::list 用 push_front 插新项，用 splice 把已有节点提到头部（不是 erase + push，避免重复构造）
std::unordered_map 的 key 是缓存 key，value 是对应 std::list<:pair v>>::iterator
淘汰时直接取 list.back()，然后从 map 中 erase 对应 key

注意 `std::list::splice` 的参数陷阱

很多人写 cache.splice(cache.begin(), cache, it) 想把 it 移到开头，结果运行时报错或行为异常——这是因为 splice 要求两个 list 是同一个对象，而传入的 it 必须属于当前 list。更隐蔽的问题是：如果用 it 之后又用了 map 的迭代器（比如 erase），it 可能失效（虽然 std::list 迭代器不因插入/删除失效，但 erase map 后若误用旧 it 就危险）。

安全写法：先 auto it_list = map.at(key) 拿到链表迭代器，再 cache.splice(cache.begin(), cache, it_list)
不要在 splice 后继续用原 it_list 做其他操作，除非确认没被 invalidate（其实一般不会，但逻辑上建议用完即弃）
如果用 C++11 之前的编译器，splice 不支持三参数形式，得用四参数：cache.splice(cache.begin(), cache, it_list, std::next(it_list))

构造函数和容量控制要提前处理 key 冲突

LRU 缓存初始化时指定容量 capacity，但很多人忽略：当 put(k, v) 时，如果 k 已存在，应该更新值并提升优先级，而不是当成新 key 处理；如果不存在且缓存已满，才淘汰尾部再插入。这个判断顺序错了就会导致容量失控或重复插入。

每次 put 先查 map.find(key) != map.end()：存在则 splice + 更新 value；不存在再看 size 是否已达 capacit y
淘汰前务必先 map.erase(list.back().first)，再 list.pop_back()，顺序反了会导致 dangling iterator
别在构造函数里预分配 list 节点——LRU 是按需增长的，预填会干扰访问序

线程安全不是默认选项，别想当然加锁

标准 std::list 和 std::unordered_map 都不保证并发读写安全。如果你的 LRU 会被多线程调用，不能只给成员函数加 std::mutex 就完事——比如 get 中查 map、取迭代器、访问 list 三个动作必须原子，否则可能拿到迭代器后 list 被别的线程 splice 走，导致解引用崩溃。

最简方案：整个操作用一个 mutable std::mutex mtx 包住，所有 public 方法加 std::lock_guard
高并发场景慎用：锁粒度太大，get 和 put 会互相阻塞，此时考虑用分段锁或无锁结构（如基于 hazard pointer 的实现），但复杂度陡增
别依赖 std::shared_mutex 做读写锁优化——因为 get 实际上也要写（要 splice），所以读多写少的优势基本不存在

真正难的不是写对单线程版，而是想清楚哪些操作必须串行、哪些可以分离。比如 key 查找和 value 构造可以挪到锁外，但链表结构调整和 map 更新必须一起锁住。

# ai # c++ # 无锁 # 标准库 # red # 成员函数 # 构造函数 # auto # mutable # public # 线程 # 多线程 # pointer # map # 并发 # 对象 # 算法 # 迭代 # 链表 # 不存在 # 很多人 # 移到 # 就会 # 都不 # 就能 # 已有 # 可以用

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】