std::unordered_map + std::list 组合做 LFU 容易超时，因未在同频链表内维护访问时序，导致 get/put 时需遍历找最久未用项，退化为 O(n)；正确做法是用双向链表按频次分桶且桶内按访问时间排序，并辅以 freq_to_list、key_to_node 和 min_freq 三者协同实现严格 O(1)。
为什么 std::unordered_map + std::list 组合做 LFU 容易超时
LFU 的核心难点不在“计数”，而在“相同频率下快速找到最久未用的项”——即当多个 key 频次相同时，必须 O(1) 拿到最老的那个。用 std::unordered_map 存 key→freq，再用 std::list 按 freq 分桶，但若每个 freq 对应一个 list，且不维护每层的 LRU 顺序，get() 或 put() 时仍需遍历 list 找 tail，退化为 O(n)。
常见错误是只按 freq 分桶，却没把“同频内的访问时间序”固化进结构里。正确做法是：每个 freq 对应一个双向链表（或 list），且该链表本身按访问时间从头到尾排列；同时用一个 map 记录每个 freq 对应的链表头节点（或迭代器），避免每次查最小 freq 都要扫描所有非空桶。
- 必须用双向链表（如
std::list）而非 vector，保证插入/删除 O(1) - 不能只存
freq → list<key></key>，还要额外维护min_freq变量，并在put()插入新 key 或get()提升 freq 时动态更新它 -
min_freq更新不是简单取 min，而是“当前最小 freq 对应的 list 是否为空”——为空则 ++min_freq，否则保持
如何用两个 map + 一个 list 实现真正 O(1) 的 LFU
关键结构是：key_to_node（unordered_map<int list>::iterator></int>）、freq_to_list（unordered_map<int list>></int>）、min_freq（int）。其中 Node 是自定义结构，含 key、val、freq。
每次 get(key)：先从 key_to_node 查到对应 node 迭代器 → 读值 → 从 freq_to_list[node->freq] 中 erase 该 node → 将 node.freq++ 后 push_back 到 freq_to_list[node->freq] → 更新 key_to_node[key] 指向新位置 → 若原 freq == min_freq 且对应 list 空了，则 min_freq++。
立即学习“C++免费学习笔记（深入）”；
-
put(key, value)时若已存在，复用get()逻辑后仅更新 val；若不存在，检查容量：满则从freq_to_list[min_freq]的 front 弹出（即最久未用的同频项），并从key_to_node删除对应 key - 新 key 的初始 freq=1，直接 push_back 到
freq_to_list[1]，并重置min_freq = 1 - 所有操作都不涉及循环遍历 freq 表，
min_freq始终有效，所以淘汰是严格 O(1)
std::list 迭代器失效陷阱与 safe erase 写法
std::list 迭代器只有在被 erase 的元素上才失效，其他迭代器均有效——这是它比 vector 或 unordered_map 更适合本场景的关键。但新手常犯错：在 erase 前没保存 next 迭代器，或误用 post-increment 导致二次 erase。
安全写法示例（在 freq_to_list[f].erase(it) 后，it 已失效，不能再用）：
auto next_it = std::next(it); // 先存 freq_to_list[f].erase(it); // it 不可再用，但 next_it 仍有效（只要没被删）
- 不要写
freq_to_list[f].erase(it++)：这会先拷贝再 increment，但 erase 后原 it 已无效，increment 行为未定义 - 不要在 erase 后继续用
it->key或类似访问：UB（undefined behavior） - 如果只是单点删除（如淘汰 head），直接
freq_to_list[min_freq].pop_front()更安全，无需迭代器管理
为什么不用 std::map 替代 unordered_map
表面上看，std::map 能天然按 freq 排序，似乎方便找最小 freq ——但实际得不偿失。因为 LFU 中 freq 变化集中于 ±1，且绝大多数操作只访问当前 key 的 freq 和 min_freq 对应的 bucket，不需要遍历或范围查询。
用 std::map 带来两个硬伤：
- 每次
freq_to_list[f]访问都是 O(log F)，F 是不同 freq 的数量（可能达 O(n)），而unordered_map是均摊 O(1) -
min_freq本可通过变量维护，用map反而让逻辑变重：你仍需检查map.begin()->first是否有效，且 erase 空 bucket 时还要调用map.erase(f)，增加分支和异常路径 - 实测在 10⁵ 操作量级下，
unordered_map版本比map快 2–3 倍，尤其在高冲突或 rehash 场景下更稳定
真正容易被忽略的是：min_freq 的维护必须和 list 空状态严格同步，哪怕一次漏判，后续所有淘汰都会错位——这不是性能问题，是正确性红线。
