直接用std::map+std::list实现LFU易超时，因频次桶查找为O(log F)、找minFreq退化为O(F)，且std::list节点迁移开销大、cache不友好；应改用vector动态桶+手写双向链表+minFreq游标实现严格O(1)。
为什么直接用 std::map + std::list 实现 LFU 容易超时
LFU 的核心是「按访问频次分组，同频次内按时间淘汰最久未用」。很多人第一反应是：用 std::map 存频次→节点链表，再用 std::unordered_map 做 O(1) 查找——逻辑没错，但实际跑 LeetCode 460 或高并发压测时容易 TLE。
问题出在两个地方：频次更新时的链表迁移开销 和 低频次桶频繁分裂/合并带来的 map 重哈希。每次 get() 都要从旧频次链表中 erase 节点、插入到新频次链表头部，而 std::list::erase(iterator) 虽然是 O(1)，但 std::map 查找目标频次桶却是 O(log F)，F 是当前最大频次；更糟的是，如果频次分布稀疏（比如只有 1、3、100 出现过），std::map 会保留大量空桶，遍历找最小频次桶时退化成 O(F)。
- 避免用
std::map管理频次桶，改用std::vector+ 游标（minFreq 指针）动态伸缩 - 每个频次桶内部不用
std::list，而用自定义双向链表节点，把prev/next直接嵌入结构体，减少内存跳转 -
get()和put()中所有操作必须严格控制在 O(1) 平摊复杂度，不能有隐式循环（比如遍历 map 找 minFreq）
如何用 std::vector 动态管理频次桶并维持 minFreq
关键不是“存多少个桶”，而是“哪些桶非空”。我们让 freqBuckets 是一个 std::vector<:list>>，下标即频次，但只在首次插入某频次时 push_back 新链表；同时维护一个整数 minFreq，指向当前含有效节点的最低频次桶。
难点在于 minFreq 怎么更新：它不能每次 get() 都扫描整个 vector。正确做法是——仅当某个桶变空且它恰好等于 minFreq 时，才把 minFreq 加 1。因为 minFreq 只可能上升（新 key 插入频次为 1；已有 key 提频次只会让旧桶少一个、新桶多一个），不会下降。
- 初始化时
freqBuckets = {{}}（下标 0 占位不用），minFreq = 1 -
put(key, value)时若缓存满，先删freqBuckets[minFreq].back()，再检查该链表是否为空：若空则minFreq++ -
get(key)成功后，将节点从freqBuckets[freq]移到freqBuckets[freq+1]，并更新其freq字段；若原桶为空且freq == minFreq，则minFreq = freq + 1
为什么必须手写双向链表节点而不是依赖 std::list
std::list 的迭代器在容器被移动或销毁时会失效，而 LFU 中节点要在不同频次链表间反复迁移。更严重的是：std::list 每个节点额外分配堆内存，导致 cache line 不友好，高频访问下性能损失明显。
手写节点结构可把频次、键、值、前后指针全塞进一个 struct，一次 malloc 分配，且支持在不破坏迭代器语义的前提下做指针重连：
struct CacheNode {
int key, val, freq;
CacheNode *prev, *next;
CacheNode(int k, int v) : key(k), val(v), freq(1), prev(nullptr), next(nullptr) {}
};
- 每个频次桶（
std::vector元素）存的是CacheNode*组成的链表头尾指针，而非std::list - 迁移节点时只需修改四个指针（原链表断开 + 新链表接入），无内存分配/释放
- 删除末尾节点时，直接取
tail->prev，无需遍历 —— 这要求每个桶维护head和tail哑节点
LeetCode 460 测试用例里最容易栽的三个坑
官方测试数据包含大量边界 case：空操作、重复 put 同 key、容量为 0、频次突增到上千。很多看似正确的实现会在第 15/22/28 个 case 失败。
-
capacity == 0时，所有put()必须立即丢弃，且不能影响后续get()（返回 -1），别忘了在构造函数里直接 return - 更新已有 key 的 value 时，
freq要 +1，但不能漏掉从原频次桶移除的动作 —— 否则同一节点会出现在两个桶里 - 当
minFreq对应的桶为空，但freqBuckets.size() 时，不能再访问freqBuckets[minFreq]，必须先freqBuckets.resize(minFreq + 1)
频次链表优化的本质不是“更炫的结构”，而是把所有潜在的 O(log N) 或隐式 O(F) 操作，压进确定的指针操作和一次 vector resize 里。真正难的从来不是写对逻辑，而是确认每一步的常数因子够不够小。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
