std::unordered_map + std::list 组合无法直接支持 O(1) 频次查找，因缺乏对各频次链表是否为空的快速判断机制，导致 min_freq 更新不可靠；需配合 freq_to_list（频次→链表）、key_to_node（key→迭代器）及独立 freq/value 表协同维护，才能实现真正 O(1) 淘汰。
为什么 std::unordered_map + std::list 组合无法直接支持 O(1) 频次查找
LFU 要求在容量满时淘汰「当前频率最小且最久未使用」的 key，关键瓶颈不在插入或访问，而在「快速定位当前最小频次」——如果每次淘汰都遍历所有 key 查最小 freq，复杂度就是 O(n)，根本谈不上高性能。
常见错误是只用一个 std::unordered_map 存值、另一个 std::unordered_map 存频次，再加个变量 min_freq 手动维护。问题在于：当某个 key 频次从 1 增到 2 后，若原 min_freq == 1 且该 key 是唯一 freq=1 的项，min_freq 就该变成 2，但你无法知道 freq=1 的 bucket 是否已清空，除非额外记录每个频次对应的 key 数量。
- 必须为每个频次维护一个双向链表（或
std::list），链表节点存 key（或 key+value） - 必须用
std::unordered_map或类似结构，让每个频次能快速访问其链表::iterator> -
min_freq只在「当前 freq bucket 为空」且「该 freq 等于 min_freq」时才需要递增，而是否为空，靠检查对应链表empty()即可
如何用 freq_to_list 和 key_to_node 实现真正 O(1) 淘汰
核心是两个哈希表协同：key_to_node 记录每个 key 对应的迭代器位置（指向它在哪个 freq 链表中的节点），freq_to_list 按频次索引链表。这样：访问 key → 查 key_to_node → 得到旧 freq 和迭代器 → 从旧 freq 链表中 erase → 插入新 freq 链表末尾 → 更新 key_to_node → 若旧 freq 链表变空且等于 min_freq，则 min_freq++。
注意：不能把 value 直接塞进链表节点，否则更新 value 时需先查再改，破坏 O(1)；推荐节点只存 key，value 和 freq 放在另一张表里（如 std::unordered_map）。
- 插入新 key 时，
min_freq = 1，直接插入freq_to_list[1]尾部 - 访问已有 key 时，先从
key_to_node获取它在freq_to_list[freq]中的位置，erase 后 push_back 到freq_to_list[freq + 1] - 淘汰时，取
freq_to_list[min_freq].front()，删掉该 key 在三张表里的所有记录 - 每次 erase 后立即检查
freq_to_list[min_freq].empty()，为真则min_freq++
std::list 迭代器失效规则与 key_to_node 安全更新要点
std::list 的迭代器只在被显式 erase() 的那个迭代器失效，其他全有效——这是该方案成立的前提。但很多人误用 list::splice() 或重复赋值导致悬垂指针。
典型错误：把 key_to_node[key] 当作普通指针反复解引用，却没同步更新它；或者在 erase() 后仍用原迭代器调用 ++it。
- 每次从链表移除节点前，必须先保存待操作的迭代器，例如：
auto it = key_to_node.at(key); - 执行
freq_to_list[old_freq].erase(it)后，it失效，不能再用；但key_to_node[key]此时仍是旧值，必须立刻重置 - 插入新位置后，用
freq_to_list[new_freq].insert(freq_to_list[new_freq].end(), key)返回的迭代器更新key_to_node[key] - 不要用
list::splice移动节点——它不返回新迭代器，且语义易混淆；老老实实用erase + insert
实际编码时最容易漏掉的三个边界条件
高频出错不是算法逻辑，而是初始化和边界处理：空缓存访问、同频次多 key 时的 LRU 行为、以及 min_freq 被意外跳过。
- 构造函数必须初始化
min_freq = 0，首次插入后设为 1；若初始min_freq = 1，后续无 key 时min_freq会卡死 - 淘汰逻辑中，不能只取
freq_to_list[min_freq].front()就删——要确保该 key 确实还存在（比如被 update 覆盖过），所以必须先通过key_to_node.count(key)双重校验 - 当多个 key 共享同一最小频次时，它们在链表中按访问时间排序（先访问的在前，后访问的在后），因此淘汰 front 是对的；但如果实现时用了
push_front而非push_back，顺序就反了
最小频次查找本身没有魔法，只是把「全局扫描」换成「局部判空」，代价是多维护一张链表索引。真正难的是让三张表在任意时刻保持一致——尤其在并发场景下，这些检查点一个都不能少。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
