标准库容器无法实现真正O(1) LFU，因其缺乏按频率分组与同频内LRU淘汰的双重链表嵌套能力；必须手写双链表结构，使每个节点同时挂载于频率链表和时序链表，并严格同步四类指针更新。
为什么标准库容器拼不出真正的 O(1) LFU？
因为 LFU 要求「按访问频率分组 + 同频内按最近访问时间淘汰」，而 std::unordered_map 只能做键值映射，std::list 无法按频率动态归类节点。硬用 map 管理频率桶，删除最低频节点时——如果该桶非空但最老项已过期，你得遍历整个桶找有效项，退化为 O(F)，F 是桶内节点数。
真正 O(1) 的关键在于：每个节点必须同时挂载在两个双向链表上——一个按频率升序的「频率链表」，另一个是每个频率桶内部的「访问时序链表」。且所有链表节点需支持 O(1) 拆入/插入，所以必须手写带前驱后继指针的结构体，不能依赖 STL 容器迭代器（失效风险高、无随机访问）。
如何用双链表嵌套实现频率桶与时序淘汰？
核心结构是三层指针关系：CacheNode 存 key/value/freq；每个 CacheNode* 同时属于：
– 一个全局的「频率桶链表」（按 freq 升序，头是最小 freq）
– 所在 freq 对应的「时序链表」（头是最近访问，尾是待淘汰）
-
freq_list是list，每个FreqBucket含freq和lru_list（list） - 每次
get()或put()命中，把节点从当前lru_list中 unlink，插入到freq+1对应的lru_list头部；若freq+1桶不存在，则新建并插入到freq_list中对应位置（需 O(1) 定位，所以用unordered_map建索引）::iterator> - 淘汰时只看
freq_list的 begin() 指向的桶，取其lru_list的 rbegin()（即最久未用项），删掉即可
get/put 操作中哪些指针操作容易漏掉？
最容易出错的是四类指针同步：节点移动时旧桶的 lru_list、新桶的 lru_list、freq_list 位置、freq 索引 map。漏掉任一，就会内存泄漏或链表断裂。
-
get(key)时：先查key_to_node，再从原lru_listunlink；若原桶变空，要从freq_listerase 该桶，并从freq_to_iter删除索引 -
put(key, value)时：若 key 已存在，除了更新 value 和 freq，还必须检查原桶是否为空——这是唯一触发freq_list删除的时机 - 新增 key 且缓存满时：淘汰只发生在
freq_list.begin()->lru_list尾部，但淘汰后必须检查该桶是否变空，否则不删桶（避免频繁重建） - 所有对
lru_list的erase()必须传 iterator，不能传 value；否则会遍历查找，破坏 O(1)
为什么不用 shared_ptr 而坚持裸指针 + 手动管理？
LFU 缓存对延迟敏感，shared_ptr 的原子计数开销在高频 get/put 下可观（实测约 8%~12% 性能损失）；且循环引用风险真实存在——CacheNode 持有指向自身所在 lru_list 迭代器的 raw ptr，而 lru_list 又持有 CacheNode*，用智能指针反而让所有权边界模糊。
裸指针可行的前提是：所有节点生命周期完全由缓存类控制，CacheNode 只在 put() 时 new，在淘汰或 clear 时 delete，中间绝不暴露给外部。只要构造/析构严格配对，就比智能指针更轻量、更可控。
真正难的不是写对逻辑，而是确保每次节点迁移都同步更新四个地方：节点自身 freq 字段、旧桶 lru_list、新桶 lru_list、freq_list 结构、freq_to_iter 索引。少一步，后续操作就会读到野指针或重复释放。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
