LFU缓存中minFreq无法O(1)定位的根本原因是其与频次桶空置状态脱节；必须通过查找存在性+判空双校验更新minFreq，且Node需含key/value/freq/prev/next/map_iter五字段保障O(1)操作。

LFU 缓存中 minFreq 无法 O(1) 定位，根本原因不是“找不到最小值”，而是它和频次桶的空置状态脱节——每次淘汰前扫 freq_to_list[1]、freq_to_list[2]… 就算用 std::map 也是 O(F)，F 是当前最大频次，LeetCode 460 直接超时。

为什么 freq_to_list[minFreq].empty() 是危险操作

用 std::unordered_map> 存桶时，freq_to_list[minFreq] 会隐式构造空链表（如果 key 不存在），污染哈希表、增加无效内存占用，且掩盖逻辑错误。

• 必须用 auto it = freq_to_list.find(minFreq) 先查存在性，再判断 it != freq_to_list.end() && it->second.empty()
• 若用 std::vector<:list>>，下标访问快，但需配合动态扩容 + max_freq 截断（如 > 1000 归入高频桶），否则内存爆炸
• minFreq 永远不会下降，只会在插入新 key 时重置为 1，或在原桶变空且等于当前 minFreq 时递增

minFreq 只能在两个时机更新

任何其他时机更新都是冗余或错误的，会导致状态不一致或性能退化。

• put(key, value) 中 key 不存在 → 立即 minFreq = 1（此时 freq_to_list[1] 必然非空）
• get(key) 或 put 提升频次后，从 freq_to_list[old_freq] 删除节点 → 若该链表变空 且 old_freq == minFreq，则 minFreq++
• 淘汰后若 freq_to_list[minFreq].empty()，需循环 minFreq++ 直到非空或越界（越界说明缓存刚清空，下次插入会重置）

如何避免淘汰时线性扫描频次桶

核心是把“找最小频次”变成“验证当前 minFreq 是否有效”，而不是重新搜索。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

• 淘汰入口处加校验：while (freq_to_list.find(minFreq) == freq_to_list.end() || freq_to_list[minFreq].empty()) minFreq++;
• 必须设上界防护，例如 if (minFreq > max_observed_freq) minFreq = 1;，其中 max_observed_freq 在每次 put 新键时更新
• 更优做法是被动擦除空桶：每次 freq_to_list[old_freq] 变空就 freq_to_list.erase(old_freq)，这样 freq_to_list.count(minFreq) 成为 O(1) 有效性断言，淘汰前可直接 assert

Node 结构体必须包含哪些字段才能支撑 O(1)

少一个字段，get 或 evict 就可能退化成 O(N)。

• int key, value：基础数据
• int freq：决定所属频次桶，不能靠链表位置反推（链表会被复用/裁剪）
• Node* prev, *next：用于在所属频次链表内 O(1) 摘除/插入（比 std::list 迭代器更稳定、cache 更友好）
• std::unordered_map::iterator map_iter：指向 cache_map 中自身条目，确保 erase 不需查找

真正容易被忽略的是：所有频次链表操作都依赖 Node::freq 和 Node::prev/next 的同步更新；一旦迁移节点时漏掉 freq++ 或指针未重置，minFreq 就彻底失效，后续淘汰会随机删错节点。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！