LFU是一种基于访问频率的缓存淘汰算法，优先淘汰访问次数最少的数据；当访问次数相同时，再淘汰最久未使用的数据。
为什么直接用 std::map 套 std::list 实现 LFU 会变慢
因为每次访问都要更新频率，而标准容器不支持 O(1) 频率桶切换：你得先从旧频率链表中删除节点，再插入到新频率链表头部——两次查找 + 两次指针操作。更糟的是，std::list::erase(iterator) 虽是 O(1)，但前提是你要拿到那个 iterator；而你在哈希表里存的若只是值或指针，就无法反向定位到它在哪个 std::list 中的迭代器位置。
真实瓶颈不在“链表操作”，而在“定位成本”。常见错误写法是缓存 std::list::iterator 到哈希表中，但一旦该链表发生 splice 或 clear，所有 iterator 会失效（C++11 后 std::list 迭代器仅在被擦除时失效，但跨链表移动仍需手动维护）。
- 别把
std::list::iterator当长期句柄用，尤其涉及多桶切换时 - 每个频率桶用独立
std::list没问题，但必须确保节点能自带所属桶信息 - 优先用裸指针 + 自定义分配器管理节点生命周期，避免智能指针引发额外原子计数开销
FrequencyNode 和 FrequencyBucket 的最小必要字段设计
LFU 的核心不是“记录访问次数”，而是“按频次分组 + 组内保序”。所以节点不需要存完整计数器，只需知道它当前属于哪个频率桶；桶本身用双向链表实现，并在头部插入、尾部淘汰——这样最老的同频项自然在尾。
关键取舍：是否在节点里存 timestamp？答案是**不存完整时间戳，改用全局单调递增序号**。因为 std::chrono::steady_clock::now() 调用有开销，且纳秒级精度对缓存淘汰无意义；而一个 static std::atomic<size_t> g_tick{0}</size_t>，每次访问只做一次 fetch_add，快一个数量级。
立即学习“C++免费学习笔记（深入）”；
-
FrequencyNode至少含：key、value、freq（当前频次）、tick（最后访问序号）、prev/next（桶内链表指针） -
FrequencyBucket只需：freq、head、tail、size；不必存桶链表指针——频率桶之间用std::map<size_t frequencybucket></size_t>索引即可 - 哈希表用
std::unordered_map<keyt frequencynode></keyt>，直接持节点裸指针，避免二次寻址
如何处理频率提升时的桶迁移（increaseFrequency）
这是最容易出错的环节：节点要从 freq=n 的桶移到 freq=n+1 的桶，但 n+1 桶可能还不存在；同时，若原桶空了，应从 std::map 中移除该桶条目，否则内存泄漏。
注意两个边界：一是首次访问时 freq 从 0→1，此时节点实际是新建插入，不属于“迁移”；二是当节点 freq 达到某个高位（比如 1000），继续增长已无区分度，可设上限截断，避免桶无限膨胀。
- 迁移前检查目标桶是否存在，不存在则新建并插入
freqMap - 从原桶 unlink 节点后，立即检查原桶
size == 0，若是，调用freqMap.erase(oldFreq) - 新节点插入目标桶时，统一插到
head后（即作为最新访问项），而非head本身——否则 head 成了哨兵节点，逻辑更清晰 - 不要在迁移过程中修改节点
freq字段后再操作链表，顺序错会导致指针错乱；应先完成链表摘除，再更新freq，最后插入新桶
淘汰策略里“同频最久未用”的真实含义
很多人误以为 LFU 的“最久未用”是指时间戳最小，其实不然：LFU 规范定义是“在相同访问频次下，选择最早加入该频次桶的那个节点”。也就是说，不是全局最久未访问，而是**在当前最高频次桶中，找尾部节点**。
所以淘汰逻辑是：遍历 freqMap 找最大 key（即最高频次），取其 tail 节点；若该桶为空，降一级再找。但更高效的做法是维护一个 maxFreq 变量，在每次 increaseFrequency 和 evict 后更新——它只减不加（除非新插入推高），且减时跳过已不存在的 freq。
- 淘汰前先 while 循环：while (
freqMap.find(maxFreq) == freqMap.end()) --maxFreq; - 取
freqMap[maxFreq]->tail即可，无需遍历所有桶 - 如果
tail是哨兵节点（推荐做法），则真正淘汰的是tail->prev，删完记得调整 tail->prev->next = tail - 千万别用
std::map::rbegin()找最大 freq——虽然语义对，但 map 的红黑树结构使 rbegin() 是 O(log N)，而维护maxFreq是 O(1)
真正难的不是写出来，而是让 increaseFrequency 和 evict 在并发场景下不出错：裸指针 + 手动链表管理意味着没有 RAII 保护，任何异常路径（比如 new 抛异常）都可能导致链表断裂。生产环境建议用 std::pmr::unsynchronized_pool_resource 配合自定义节点分配器，把所有节点内存划到一块池里，既提速又防碎片。
