std::unordered_map + std::list 无法直接实现 LFU 的 O(1) 频率更新，因为缺乏按频次有序组织的结构，无法 O(1) 定位当前最小频次对应的所有键；必须用 freq→list 分桶 + key→iterator 双映射 + min_freq 维护才能达到均摊 O(1)。
为什么 std::unordered_map + std::list 无法直接实现 LFU 的 O(1) 频率更新
LFU 要求每次 get 或 put 后，键的访问频次 +1，且同频次的键需按最近使用时间排序（用于淘汰）。若用 std::list 存键值对、std::unordered_map 存 key→iterator 映射，能 O(1) 删除/移动节点，但**无法 O(1) 定位「当前最小频次对应的所有键」**——因为频次是离散变化的，没有天然有序结构支撑快速取 min_freq。常见错误是只维护一个 list，结果 evict 时遍历找最小频次项，退化为 O(n)。
实操建议：
- 必须分离「频次维度」和「时间维度」：用
std::unordered_map按频次分桶，每个桶内 list 按访问时间倒序（新访问的插在 front）> - 额外维护
int min_freq，每次get/put后检查是否需更新：若 min_freq 对应的 bucket 为空，则min_freq++ - Node 结构里必须存
key、value、freq，不能只存 value——否则从 list 中删节点后，无法反查 key 来更新 freq map
如何让 get/put 真正达到均摊 O(1) 时间复杂度
关键不在单个操作，而在「避免重复扫描」。例如 get(key) 时，不能先查 freq map 得到旧频次 f，再从 bucket[f] 中找节点（O(bucket_size)），而应让每个 key 直接指向其在对应 bucket 中的 iterator。
实操建议：
- 用两个 map：
std::unordered_map（key → 迭代器），::iterator> std::unordered_map（freq → 节点链表）> -
get(key)步骤：① 查 key→iter，若无返回 -1；② 从旧 bucket[f] 中 erase iter；③ 将 node.freq++，插入 bucket[f+1].front()；④ 更新 key→iter 映射；⑤ 若 bucket[f] 为空且 f == min_freq，则 min_freq++ -
put(key, value)类似，但若 key 已存在，只更新 value 和 freq；若不存在且 size == capacity，则先evict()：从 bucket[min_freq].back() 弹出，删 key→iter 映射，再插入新 key
evict() 时为什么必须从 bucket[min_freq].back() 而不是 front() 删除
因为每个 bucket 内部 list 是按「最近访问时间倒序」维护的：新访问的节点插入 front()，最久未访问的在 back()。LFU 规则要求「相同频次下淘汰最久未使用的」，所以必须取 back()。若误用 front()，会导致刚被访问过的键被立刻淘汰，命中率断崖下跌。
容易踩的坑：
- 没在 Node 中存
key，导致从bucket[min_freq].back()取出 node 后，无法知道该删哪个 key 的映射，引发内存泄漏或后续get崩溃 - evict 后忘记更新
min_freq：比如原 min_freq=2 的 bucket 刚被清空，但没检测就继续用 2，下次 put 时可能往空 bucket 插，或漏判新 min_freq - capacity == 0 的边界没处理，导致构造时直接崩溃
C++17 下避免 shared_ptr 带来的引用计数开销
有人用 std::shared_ptr 存 iterator 映射，以为更安全，但每次 get 都触发原子增减，性能损失明显（尤其高并发场景）。实际完全不需要：Node 生命周期由 list 保证，iterator 在 list 不重排时稳定有效。
实操建议：
- 用裸指针或直接存
std::list（推荐），只要确保不发生 list splice/rehash 即可——而我们只做 push_front/erase/splice，STL list 迭代器不会失效::iterator - 若担心迭代器悬空，可在 Node 中加
bool valid = true标记，erase 前设为 false，get 时检查（但通常冗余） - 避免在 Node 中存
std::string或大对象，用std::string_view+ 外部生命周期管理，或 move 构造减少拷贝
缓存淘汰逻辑真正难的不是写对，而是让 min_freq 和各 bucket 的非空状态始终同步——哪怕一次漏判，后续所有 evict 都会错。调试时建议打日志输出每次操作后的 min_freq 和各 bucket.size()，比断点更直观。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
