不能直接用 std::map + std::list 实现高效 LRU，因 map 无法直接定位 list 节点；正确做法是 map 存 key → list::iterator，配合 splice 移动节点并同步更新，推荐用 unordered_map 提升查找至 O(1)。
为什么不能直接用 std::map + std::list 做 LRU？
因为 std::list::erase(iterator) 是 O(1)，但你得先找到那个要删的节点——而 std::map 存的是 key → value，不是 key → list iterator。如果每次 get() 都去遍历 list 找对应节点再移到头，就退化成 O(n) 了。
真正可行的做法是：让 map 存 key → list::iterator，这样查位置是 O(log n)，移动节点是 O(1)。
-
std::list存的是std::pair<const key value></const>（或自定义结构），保证值可访问 -
std::map存的是Key → std::list<...>::iterator，实现快速定位 - 所有更新操作（
get/put）都需同步修改 map 中的 iterator 指向
put() 时如何正确更新 list 和 map？
关键在于：新元素必须插到 list 头（最近使用），旧元素若存在，得先从 list 中擦除原节点，再插入新节点，并更新 map 中的 iterator。
注意：不能直接用 list.push_front({k, v}) 后再存 iterator，因为 list 迭代器在后续插入/删除中不会自动失效，但你得确保 map 里存的是当前有效的 iterator。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 先查 map：若 key 已存在，用
list.erase(map[k])删除旧节点 - 再
list.push_front({k, v})，然后map[k] = list.begin() - 若 size 超限，删
list.back()，并从 map 中 erase 对应 key：map.erase(list.back().first)，再list.pop_back() - 顺序不能错：删 map 必须在删 list 之前（否则
list.back().first可能已无效）
get() 的陷阱：iterator 失效和 map 更新漏掉
很多人只做 map.find() + 返回值，却忘了把对应节点提到 list 头——这就不是 LRU，只是带缓存的查找。
更隐蔽的问题是：list.splice() 比 erase()+push_front() 更安全，因为它不涉及内存重分配，iterator 不会失效；但如果你用后者，必须确保 map 中旧 iterator 在 erase 后不再被访问。
- 查不到直接 return -1
- 查到了，先用
auto it = map[key]拿到 list 迭代器 - 用
list.splice(list.begin(), list, it)把该节点移到开头（高效且安全） - 再更新 map：由于
splice不改变 iterator 有效性，map[key] = list.begin()即可（注意：it此时仍有效，但指向旧位置，别误用）
为什么不用 std::unordered_map？
可以，而且更推荐——O(1) 平均查找比 std::map 的 O(log n) 更好。但要注意：迭代器稳定性不变，unordered_map 的 erase 不会使其他 iterator 失效（除非 rehash），所以它和 list 配合完全没问题。
唯一代价是额外哈希计算和可能的内存碎片，对一般 LRU 场景影响极小。
- 把
std::map<Key, std::list<...>::iterator>换成std::unordered_map<Key, std::list<...>::iterator> - 确保
Key有合法的std::hash和operator== - 如果 key 是自定义类型，别忘了特化
std::hash，否则编译失败：错误信息类似error: call to implicitly-deleted default constructor of 'std::hash<mykey>'</mykey>
