std::unordered_map+list仅支持lru，lfu需频次分组：外层freq_list按频次升序链接freqbucket，内层自定义双向链表存cachenode并维护bucket指针，确保get/put均o(1)。
为什么 std::unordered_map + list 不够用？
直接用 std::unordered_map 存 key→value，再用 std::list 维护访问顺序，只能做 LRU；LFU 要按「频次分组」，同一频次的节点必须能 O(1) 插入、O(1) 摘除、O(1) 提升频次——链表单层结构无法支持频次跳跃（比如从 freq=2 直接升到 freq=3 的头部），更无法在频次降级时快速定位目标频次链表。
真正可行的结构是「频次链表套节点链表」：外层是按 freq 升序排列的 freq_list，每个节点指向一个 freq_bucket（即该频次下的双向链表）；内层每个 bucket 用自定义双向链表（非 std::list）管理 key 和 value，保证删除/移动不依赖迭代器失效。
- 避免用
std::list::erase(iterator)做频次提升：它需要先 find 再 erase，O(n) - 每个
CacheNode必须存指向其所在 bucket 的指针（或引用），否则升频时无法 O(1) 定位源 bucket - 外层
freq_list推荐用std::list<freqbucket></freqbucket>，但插入新 bucket 时要检查前驱是否已存在 freq−1，不存在就得新建并插入正确位置
如何让 get() 和 put() 都做到 O(1)？
核心在于三张表协同：key_to_node（std::unordered_map<key cachenode></key>）提供 key→节点直查；node_to_bucket（可合并进 CacheNode 成员）避免查桶开销；外层 freq_list 仅用于快速获取最小 freq 对应的 bucket（淘汰时用）。
每次 get(key)：查 key_to_node → 取出节点 → 从原 bucket 摘下 → 插入 freq+1 的 bucket（若不存在则新建并插入 freq_list 正确位置）→ 更新节点 freq 和 bucket 指针 → 返回 value。
put(key, value)：若 key 已存在，同 get 流程更新 value 并升频；若不存在，先检查容量，若满则淘汰 freq_list.front()->lru_tail（即最小 freq 中最久未用的节点），再新建节点插入 freq=1 的 bucket（同样要确保 freq=1 bucket 存在）。
- 淘汰必须取
lru_tail（不是 head），因为 bucket 内部是 LRU 序：新访问插 head，淘汰取 tail - 新建 freq bucket 时，不能只 push_back 到
freq_list，得遍历找 freq−1 位置再 insert_after，否则频次链表乱序，min_freq 无法 O(1) 获取 - 所有链表操作（摘除/插入）必须裸指针或自定义链表节点，禁用
std::list迭代器，否则 move/erase 后迭代器失效，无法维护 node→bucket 映射
为什么自定义双向链表比 std::list 更合适？
std::list 的节点内存布局不可控，且迭代器在 erase 后立即失效，而 LFU 中一个 CacheNode 在升频时需先从旧 bucket 删除、再插入新 bucket——这要求「删除时不破坏节点自身数据，且插入前能稳定访问该节点」。
自定义节点如：
struct CacheNode {
Key key;
Value value;
int freq;
CacheNode* prev;
CacheNode* next;
FreqBucket* bucket; // 关键：反向定位所属 bucket
};
这样，升频时直接 old_bucket->remove(node)（仅改指针），再 new_bucket->push_front(node)，全程无内存分配/释放，无迭代器生命周期问题。
- 不要把
prev/next封装成std::unique_ptr：增加间接访问开销，且 delete 时机难控 - 每个
FreqBucket必须维护head和tail指针，并记录 size，方便满容时快速判断是否需淘汰 - 空 bucket 必须及时从
freq_list中移除，否则 min_freq 可能指向已无节点的 bucket，导致误淘汰
容量变化和频次重置会引发什么隐性 bug？
当调用 set_capacity(new_cap) 且 new_cap 时，不能简单清空 map 后重建——必须按 LFU 规则淘汰至 ≤ new_cap，即反复执行「取 min_freq bucket 的 tail 节点 → 删除 → 更新 key_to_node」直到 size ≤ new_cap。
更隐蔽的是「频次重置」需求：某些场景（如监控周期重置）要求所有节点 freq 归 1。此时不能遍历所有节点改 freq 字段，因为 bucket 指针仍指向旧 freq bucket，会导致链表错位。正确做法是：对每个节点，先从原 bucket 移除，再插入 freq=1 bucket，并更新 bucket 指针。
- 不要在
CacheNode析构时自动从 bucket 解绑：析构可能发生在 remove() 之后，重复解绑 crash - 所有指针操作（
prev/next/bucket）必须显式置 nullptr，尤其在 remove() 后，防止野指针访问 - 多线程场景下，即使只读的
get()也需考虑 freq 更新的原子性（freq++非原子），建议用std::atomic_int存 freq
实际写的时候，最容易漏掉的是 bucket 空了不清理、新 freq bucket 插入位置错、以及 node 的 bucket 指针没同步更新——这三个点一出，缓存行为立刻偏离 LFU 语义，变成随机淘汰。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
