用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，这样通过 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 处理；如果不存在且缓存已满，才淘汰尾部再插入。这个判断顺序错了就会导致容量失控或重复插入。
立即学习“C++免费学习笔记（深入）”；
- 每次
put先查map.find(key) != map.end()：存在则splice+ 更新 value；不存在再看 size 是否已达capacity - 淘汰前务必先
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 更新必须一起锁住。