用std::list+std::unordered_map实现O(1)LRU的核心是利用list的splice支持O(1)节点移动且迭代器不失效，map存key到list迭代器映射实现O(1)查找；每次get/put命中均用splice移至头部，满容时先取尾部key删map再pop_back，严禁erase+push_front或误序删除。
用 std::list + std::unordered_map 实现 O(1) LRU
LRU 的核心是「访问即置顶」+「容量满时删尾部」，必须支持快速查找、删除任意节点、移动节点到头部。C++ 标准库里没有现成的双向链表+哈希组合结构，但 std::list 支持 splice（O(1) 移动节点），std::unordered_map 存键到 std::list 迭代器的映射，就能达成平均 O(1) 的 get 和 put。
关键不是手写链表，而是利用 std::list 的迭代器稳定性：插入/删除其他节点不会使已有迭代器失效，所以 map 里存的迭代器长期有效。
实操建议：
- 定义
std::list<:pair int>></:pair>存 {key, value}，头部为最近访问，尾部为最久未用 -
std::unordered_map<int std::list int>>::iterator></int>快速定位 key 对应的节点位置 - 每次
get或put命中时，用splice(list.begin(), list, it)把对应节点移到头部（不是 erase + push_front） -
put时若容量超限，先删list.back()，再从 map 中 erase 其 key
为什么不用 std::vector 或 std::deque
std::vector 删除中间元素是 O(n)，且迭代器在增删后极易失效；std::deque 虽支持头尾 O(1)，但不支持任意位置 O(1) 移动节点——你没法把中间某元素“拎出来插到开头”而不遍历或拷贝。而 LRU 每次访问都要重排顺序，高频操作下性能差距明显。
立即学习“C++免费学习笔记（深入）”；
常见错误现象：
- 用
vector存缓存项，每次get后erase再insert(begin(), ...)→ 实际是 O(n) 时间，且反复内存搬移 - map 里存索引（int）而非迭代器 →
vector一删，所有后续索引偏移，map 中旧索引立刻失效 - 误以为
deque::erase是 O(1) → 它对非头尾位置仍是 O(n)
put 时 key 已存在该怎么处理
标准 LRU 要求：更新 value 同时刷新访问时间（即把该节点提到链表头）。很多人只改了 map 中的 value，却忘了调整链表顺序，导致该 key 在下次淘汰时被误删。
正确做法是统一走「先删后插」逻辑，而不是分支判断：
- 如果 key 存在：用 map 找到对应
list迭代器 →splice到头部 → 更新 value（直接改it->second） - 如果 key 不存在：检查容量 → 满则先删尾部 →
push_front新节点 → 更新 map
注意：不要在 put 里对已存在 key 单独写一个 update 分支，容易漏掉 splice 步骤。统一用「查→移→改」三步更可靠。
线程安全不是默认选项，别假设有锁
上面所有实现都是单线程安全的。一旦多个线程并发调用 get/put，std::list 和 std::unordered_map 都会出数据竞争——比如两个线程同时 splice 同一节点，或 map 插入时触发 rehash 导致所有迭代器失效。
如果你需要多线程 LRU：
- 最简单是加一把全局
std::shared_mutex（读写锁），get用 shared_lock，put用 unique_lock - 避免用
std::mutex全局锁，否则读多写少场景下吞吐骤降 - 别尝试无锁实现——LRU 天然依赖顺序和状态一致性，自己写 lock-free 链表+哈希极易引入 ABA 或内存泄漏
真正容易被忽略的是：哪怕只读的 get，在无保护下调用 map::find + list::splice 也是不安全的，因为 splice 修改了 list 结构，可能干扰其他线程正在做的遍历。
