必须用 std::list + std::unordered_map 组合，因其唯一能同时满足 o(1) 查找、o(1) 移动到头部、o(1) 淘汰尾部；std::list 支持双向遍历与迭代器稳定，std::unordered_map 提供 key 到迭代器的快速映射。
为什么必须用 std::list + std::unordered_map 组合
因为只有这个组合能同时满足三个硬性要求：O(1) 查找、O(1) 移动到头部、O(1) 淘汰尾部。用 std::vector 或 std::deque 都会破功——前者删中间元素是 O(n)，后者迭代器在插入/删除后可能失效，导致 cache_map[key] 解引用野指针。
-
std::unordered_map提供 key → list 迭代器的映射，get 时不用遍历就能定位节点 -
std::list是双向链表，push_front、erase(iterator)、begin()、end()全是常数时间 - 不能用
std::forward_list：它不支持反向遍历，无法高效删尾（得从头遍历到倒数第二项）
put 时 key 已存在，只改 value 就完事？错
这是最常见逻辑漏洞：只更新 cache_map[key]->second，却没把对应节点从原位置移走再插到头部。结果是链表顺序错乱，cache_list.back() 不再代表“最久未用”，淘汰机制彻底失效。
- 正确流程是：先用
cache_map.find(key)判断存在 → 若存在，用cache_map[key]获取迭代器 →cache_list.erase(it)删除旧位置 →cache_list.push_front({key, value})插入新节点 →cache_map[key] = cache_list.begin()更新映射 - 注意：
push_front返回的是新节点迭代器，必须立刻存进 map；如果 erase 后忘了这步，后续get会解引用已失效迭代器，触发未定义行为 - 别省略
erase：即使 value 相同，访问顺序也要重置，LRU 的语义是“最近访问”，不是“最近写入”
用 std::pair<int int></int> 还是自定义 struct？
初期验证逻辑用 std::pair 没问题，但上线前务必换成命名清晰的结构体。这不是风格问题，是维护成本问题。
-
std::pair写起来快：it->first、it->second容易看混，尤其当缓存要扩展字段（比如加timestamp或ref_count）时，代码迅速不可读 - 结构体零开销：
struct CacheNode { int key; int val; };和std::pair在内存布局、移动性能上完全一致，都是 trivial 类型 - 别为“未来可能加字段”提前设计复杂类——先跑通核心逻辑，再按需重构；但一旦进入生产环境，
it->first就是埋雷点
容量满时删尾节点，cache_list.back() 能直接用吗？
不能直接用。因为 std::list::back() 返回的是值引用，不是迭代器；而你要删的是节点本身，且删完还要从 unordered_map 中清除对应 key，必须拿到该节点的迭代器。
立即学习“C++免费学习笔记（深入）”；
- 正确做法是：用
auto tail_it = std::prev(cache_list.end())获取尾节点迭代器（end()是 past-the-end，前一个是真实尾） - 然后
int key_to_erase = tail_it->key;提取 key →cache_list.erase(tail_it);→cache_map.erase(key_to_erase); - 别写
cache_list.pop_back()：它删值但不告诉你删的是哪个 key，map 里残留脏数据，下次put同 key 会覆盖 map 但链表里还留着旧节点
真正难的不是写对那几行代码，而是时刻记住：map 存的是迭代器，不是值；list 迭代器一删就废，不能缓存、不能复用、不能跨操作保留；所有操作必须 map 和 list 严格同步——差一行，缓存就“失忆”。
