lfu不能仅用unordered_map加计数器实现o(1)是因为需同时维护频次与访问时序，而单map无法在最小频次下o(1)定位最久未用key；标准解法需双哈希表+按频次分桶的双向链表，并维护min_freq变量。
为什么 LFU 不能只靠 std::unordered_map + 计数器实现 O(1)
因为 LFU 要在「访问频次相同」的多个 key 中，淘汰「最久未使用」的那个——这要求同时维护频次和时序两个维度。只用 unordered_map 存 key → frequency，无法在 O(1) 内定位当前最小频次下最老的 key；手动遍历找最老项会退化到 O(n)。
核心结构：双层哈希 + 链表分频次桶
标准 O(1) LFU 实现依赖两个关键结构：
-
key → (freq, list_iterator)映射（std::unordered_map），用于 get/put 定位 -
freq → std::list<key></key>（也用unordered_map存），每个频次对应一个双向链表，新 key 插入链表尾，淘汰时从链表头取 - 额外维护一个
min_freq变量，记录当前所有存活 key 的最小频次
每次 get(key)：查出原频次 f，从 freq2list[f] 中删掉该 key，插入 freq2list[f+1] 尾部；若 freq2list[f] 变空且 f == min_freq，则 min_freq++。
每次 put(key, value)：若 key 已存在，同 get 更新频次；否则，若缓存满，从 freq2list[min_freq] 头部删一个 key，再插入新 key 到 freq2list[1]，并设 min_freq = 1。
std::list 迭代器为何能 O(1) 删除？
因为 std::list 是双向链表，迭代器直接指向节点，erase(iterator) 不需要查找，就是解链操作，严格 O(1)。但注意：std::vector 或 std::deque 的 erase 不行——前者要搬移元素，后者不保证 O(1) 迭代器删除。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
常见错误是把 key 存进 vector 后靠值查找再删，这会破坏 O(1)；必须用 list + 迭代器持久化保存位置。
容易被忽略的边界：min_freq 更新时机
min_freq 只在两种情况下更新：
- 新插入 key 时，设为 1（此时缓存可能刚清空）
-
get或put导致某个freq2list[f]变空，且f == min_freq，才执行min_freq++
漏掉第二种情况，会导致后续淘汰始终从空链表取，或者误删高频 key。另外，min_freq 永远不会自动「下降」——没有 key 被降频，只有新增或升频，所以不需要主动减它。
实际编码时，建议把 freq2list[f].empty() 检查和 min_freq 更新绑在一起，不要分散在多处逻辑里。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
