std::unordered_map + std::list 实现 lfu 易超时，因无法 o(1) 维护「频率升序+同频时间升序」双维度；常见遍历找 minfreq 或用 std::map 管理桶均退化为 o(n) 或 o(log f)，且频繁 splice 导致性能抖动。
为什么 std::unordered_map + std::list 做 LFU 容易超时
因为标准容器组合无法在 O(1) 时间内完成「按频率升序 + 同频按访问时间升序」的双维度维护。常见写法是每次 get() 或 put() 后遍历链表找最小频率节点，退化成 O(n)；或者用 std::map<int list>></int> 管理频率桶，但 std::map 的 begin() 虽快，删除非首尾节点仍需 O(log F)（F 为不同频率数），且频繁移动节点会触发大量 list splice 操作，实际性能抖动大。
核心结构：frequency map + freq bucket list + node 指针反查
必须拆开三个层级：
-
unordered_map<int node></int>：key → node 指针，支持O(1)查找 -
list<list>></list>：外层链表按频率递增排列，每个节点是一个同频 bucket（list<node></node>） -
unordered_map<int list>>::iterator></int>：频率 → 对应 bucket 在外层链表中的位置，避免每次找 minFreq 都从头遍历
关键点：每次 get() 时，把 node 从当前 bucket 移到 freq+1 bucket 尾部（保证同频 LRU），并更新 minFreq —— 如果原 bucket 空了且它正好是当前 minFreq，则需推进 minFreq 到下一个非空 bucket（靠上面的 frequency map 快速定位）。
put() 中淘汰策略与 minFreq 更新的边界条件
淘汰只发生在 put() 且缓存已满时，必须删掉「最低频 + 最久未用」的节点，即 minFreq bucket 的 front() 节点。但注意：
- 如果新 key 不存在，插入后 size 加一；若因此超限，立刻淘汰，再继续后续逻辑
- 如果新 key 已存在，只是更新 value 和频率，不触发淘汰，也不改变 size
- minFreq 初始值设为 0，首次插入后置为 1；后续仅当「当前 minFreq bucket 变空」且「没有更高 freq 的 bucket 存在」时才需要重扫——但有 frequency map 就不用扫，直接查
freq_to_bucket_map[minFreq]是否还有效即可
漏掉「bucket 空了但 minFreq 没及时更新」会导致后续淘汰删错节点，这是最常踩的坑。
完整代码中不可省略的细节处理
以下几处不加判断必然出错：
- node 构造时必须同时初始化
key、value、freq，否则put()复用旧 node 会残留脏数据 - 从 bucket 中
erase()node 前，必须先用bucket.erase(it)（it 是 list::iterator），不能直接用 node 地址去 unordered_map 里删 —— 因为 node 本身不带迭代器信息 - 移动 node 时，要用
bucket.splice(bucket.end(), old_bucket, it)，而不是先erase再push_back，否则破坏迭代器有效性 - 所有对
freq_to_bucket_map的修改（insert/erase）必须和外层 list 的操作严格同步，否则 map 里存了已销毁的 iterator
LFU 的复杂度优势全系于这些指针和迭代器的精准控制，稍有松动就退化成模拟题级别实现。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
