纯用std::unordered_map或std::list单独实现LFU无法达到均摊O(1)；必须采用双映射（key→Node+iter、freq→list）、频次分桶、显式维护list迭代器及动态min_freq，否则get/put将退化为O(n)或崩溃。
纯用 std::unordered_map 或 std::list 单独实现 LFU，不可能达到均摊 O(1) 时间复杂度；必须用双映射 + 频次分桶 + 显式迭代器维护，否则 get/put 会退化成 O(n) 或频繁崩溃。
为什么 std::unordered_map + std::list 组合无法支撑 LFU 的 O(1) 频次更新
LFU 要求每次 get() 或 put() 后，键的频次 +1，并能 O(1) 定位「当前最小非空频次对应的所有键」。若只用一个 std::list 存所有节点、一个 std::unordered_map 存 key → iterator，你能快速删节点、插头尾，但无法回答这个问题：「现在哪个频次最低且链表非空？」
常见错误做法：
- 维护一个
min_freq变量，但不检查其对应链表是否已空 → 后续evict()调用bucket[min_freq].back()时触发未定义行为 - 频次提升时，只改
node.freq，没从旧桶erase(iter)→ 节点在两个桶里同时存在，数据错乱 - 用
freqMap[key] = freq外部存频次，导致每次迁移都要查两次哈希表（先找 node，再查 freq），破坏 O(1) 假设
Node 结构体必须包含哪些字段才能避免迭代器失效和逻辑错乱
只放 key、value、freq 是不够的；缺少对自身位置的反向引用，就无法安全地从任意频次桶中摘除节点。
正确字段组合（缺一不可）：
-
int key,int value：基础数据 -
int freq：当前访问频次，决定它属于哪个桶 -
std::list：指向它在所属频次链表中的位置（不是指针！是迭代器）::iterator iter
关键约束：
-
iter必须在节点插入链表后**立刻赋值**，例如：auto it = bucket[freq].emplace_front(node); node.iter = it; - 每次从链表中
erase(node.iter)后，该iter立即失效，不能再用；后续插入新桶时需重新赋值 - 不能把
iter存成裸指针或void*——std::list迭代器不是稳定地址，重分配后失效
如何安全更新 min_freq 并防止淘汰阶段崩溃
min_freq 不是静态最小值，而是动态游标；它只在两种时刻被修正：新增 key 时强制设为 1，或某次频次迁移后旧桶变空且旧频次等于当前 min_freq。
更新规则：
-
put(key, value)新增节点时：min_freq = 1 -
get(key)或put更新已有 key 时：先从bucket[old_freq]中erase(node.iter)，再检查bucket[old_freq].empty()；若为真且old_freq == min_freq，则min_freq++ -
evict()执行前，必须确认bucket[min_freq]非空；若为空，需循环min_freq++直到非空或越界（此时缓存已空）
典型坑：
- 在
evict()里直接写bucket[min_freq].back()，不加空检查 →std::list::back()对空容器是未定义行为 - 误以为
min_freq可以通过遍历freqMap键集获取 → 那是 O(F)，F 是历史最大频次，完全违背设计目标 - 多线程场景下未加锁或用原子变量保护
min_freq→ 一个线程刚清空桶，另一个线程还没推进min_freq就开始淘汰，踩空
淘汰时为什么必须取 bucket[min_freq].back() 而不是 .front()
每个频次桶内部的 std::list 是按 LRU 规则组织的：新访问的节点插在 front()，最久未访问的自然沉到 back()。LFU 规则明确要求「相同频次下淘汰最久未使用的」，所以必须取尾。
实操细节：
- 插入新节点或频次提升节点时，统一用
bucket[freq].emplace_front(...)，保证时间序 - 不要用
push_back()再手动splice到头 —— 多一次操作，易出错 - 如果引入时间戳做更精细排序（如
std::chrono::steady_clock::now()），仍应保持尾部是最小时间戳，否则back()语义失效
真正难的不是写对单个操作，而是让 min_freq、iter、freq 三者始终同步；任何一个字段滞后一步，整个缓存就会开始淘汰高频 key 或 crash。这种状态一致性，比算法本身更消耗调试时间。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
