用std::list+std::unordered_map实现o(1)lru：list保证节点移动/删除o(1)，map存key到list迭代器映射实现o(1)查找；节点须封装key/value；淘汰时先用尾节点key删map再删list；deque迭代器易失效故不可替代list；需加锁保障线程安全。
用 std::list + std::unordered_map 实现 O(1) 增删查
LRU 的核心是「最近最少使用」，必须支持快速定位、快速移到头部（表示最近访问）、快速淘汰尾部。单纯用 std::map 或 std::vector 都做不到所有操作平均 O(1)。std::list 保证节点删除/移动是 O(1)，std::unordered_map 存键到链表迭代器的映射，实现 O(1) 查找——这是最常用且可靠的做法。
关键点：
- 不要用
std::list::iterator直接存值（比如int），要封装成结构体，包含key和value，否则删除尾部时无法反查 key 来清理 map -
std::unordered_map的 value 类型必须是std::list<node>::iterator</node>，不是Node*或索引——因为 list 迭代器在插入/删除时不失效（只要不删它自己） - 每次
get()或put()命中，都要把对应节点用splice()移到list头部，而不是 erase + push_front：前者保持迭代器有效，后者会令 map 中原有迭代器失效
put() 中缓存满时的淘汰逻辑怎么写才安全
缓存满（map.size() == capacity）时，不能先删 list.back() 再删 map，也不能反过来——必须严格按顺序：先从 list 尾部取 node，用它的 key 去删 map，再删 list 节点。否则 map 里残留一个指向已销毁内存的迭代器，后续 get() 会崩溃。
典型错误写法：cache_list.pop_back(); cache_map.erase(cache_list.back().key); —— 这里 pop_back() 后 back() 已非法。
正确顺序：
- 取尾部节点：
auto& last_node = cache_list.back(); - 删 map：
cache_map.erase(last_node.key); - 删 list：
cache_list.pop_back();
为什么不用 std::deque 替代 std::list
std::deque 支持 O(1) 头尾操作，但它不保证迭代器在插入/删除时稳定——中间插入或头尾频繁操作后，已有迭代器可能失效。而 LRU 中 map 保存的正是 list 迭代器，一旦失效，get() 时解引用就 UB（未定义行为），常见表现是段错误或随机值。
对比：
-
std::list::iterator：只要不显式erase()它自己，就永远有效 -
std::deque::iterator：任何push_front()/push_back()都可能让其他迭代器失效（标准未保证） - 哪怕你只用头尾操作，不同 STL 实现行为不一，线上环境容易踩坑
线程安全要自己加锁，STL 容器默认不保证
std::unordered_map 和 std::list 的单个操作都不是线程安全的。如果多个线程同时调用 get() 和 put()，即使只是读操作（如 map.find()），也可能因 rehash 或 list 调整内部结构而触发写冲突。
简单做法是整个 LRU 类加一把 std::shared_mutex（C++17）或 std::mutex：
- 所有 public 方法入口加
std::lock_guard<:mutex></:mutex> - 别试图只锁部分代码段——
find() → erase() → insert()是典型的检查后执行（check-then-act）模式，必须原子 - 如果对性能极度敏感，可考虑分段锁或读写锁，但绝大多数场景一把互斥锁足够
真正容易被忽略的是：很多示例代码直接贴出无锁版本，跑单元测试没问题，一上多核服务就偶发 crash 或数据错乱——这不是概率低，是必然发生，只是时机难复现。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
