std::unordered_map + std::list 组合无法真正支持 o(1) lfu 查找最小频率，因 minfreq 变量在桶清空后失效，需遍历重算；o(1) 解法是用升序 list 存非空桶、unordered_map 映射频率到迭代器，并为每个节点维护双指针实现频率升级搬运。
为什么 std::unordered_map + std::list 组合无法真正支持 O(1) LFU 查找最小频率
因为 LFU 的核心瓶颈不在“插入”或“更新”，而在于「实时获取当前全局最小频率」。常见实现用一个变量 minFreq 记录，但删除操作（如缓存满时踢出）后，它可能失效——比如某个频率为 2 的桶刚被清空，minFreq 却还卡在 2，导致下一次踢出仍去查空桶，不得不遍历所有频率桶来重算，退化成 O(F)，F 是不同频率总数。
真正的 O(1) 最小频率维护，必须让「频率桶的活跃状态」可被快速感知。解决方案是：用 std::list 存储按频率升序排列的非空桶，每个节点是 freq_t（含频率值和对应 std::list 键值对），同时用 std::unordered_map 映射频率 → 迭代器（指向该 list 节点）。这样：
-
minFreq就是 list 的front().freq，O(1) - 某频率桶变空时，用保存的迭代器直接
erase对应节点，O(1) - 新频率首次出现时，插入到 list 尾部（因频率只增不减，升序可维持），O(1) 平摊
如何让键值对在频率升级时 O(1) 搬运到更高频桶
关键不是移动数据，而是避免拷贝和重哈希。每个缓存项（CacheNode）需自带两个指针：freq_iter（指向其所在频率桶的 std::list 节点）和 kv_iter（指向该桶内具体 std::list 元素）。升级时：
- 从原桶的
std::list中用erase(kv_iter)移除，O(1) - 检查目标频率桶是否存在：查
freq_map；若无，则新建桶并插入到频率 list 尾部 - 将节点
push_back到目标桶的std::list，更新kv_iter - 更新
freq_iter指向新桶节点（来自freq_map[newFreq]）
注意：所有 std::list::iterator 在被 erase 后立即失效，所以必须在 erase 前拿到下一个位置，或像上面那样只用它做单次删除。
get() 和 put() 中频率更新的边界条件有哪些
看似简单，但三处极易出错：
-
get()命中但缓存为空（capacity == 0）：不能插入，但规范要求返回 -1，且不触发任何更新 —— 此时连访问计数都不该加 -
put()写入已存在 key：必须先完成一次get()等效动作（提升频率 + 更新 value），再返回；不能直接覆盖 value 而忽略频率变更 -
put()触发淘汰时：必须淘汰minFreq桶中最久未使用的项（即该桶std::list的front()），而非任意项；且淘汰后要立刻检查该桶是否变空，若空则同步清理freq_map和频率 list 节点
漏掉任一条件，都会导致频率统计漂移或缓存一致性破坏，后续 get() 可能命中错误 value 或崩溃（野指针）。
为什么不用 std::map<int list></int> 替代频率 list + hash map 组合
因为 std::map 的 begin() 虽然 O(1)，但删除一个 key 后，无法保证 begin() 就是新的最小频率 —— 它只是红黑树最左节点，而你删的可能是中间某个频率，此时 begin() 不变，但实际最小频率可能已升高。更糟的是，std::map::erase(iterator) 后，其他迭代器可能失效（C++ 标准未保证），而你需要稳定持有“当前桶”的迭代器用于后续操作。
相比之下，手写频率 list + freq_map（unordered_map<int list>::iterator></int>）把「桶存在性」和「升序关系」解耦：list 保证顺序，hash map 保证定位，两者各自迭代器均稳定、删除安全。
这个设计多 2 个指针、1 个额外 map，但换来严格 O(1) 所有操作，且无隐藏遍历风险 —— 复杂点全在初始化和淘汰路径的指针联动上，一旦写对，后续极难出 bug。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
