C++实现高性能LFU缓存淘汰机制核心算法 _ 频率链表与时间复杂度【源码】-C++-PHP中文网

LFU缓存不能只靠std::map或std::unordered_map实现，因其需在相同频次下按LRU顺序淘汰且频次变更时O(1)移动节点，必须结合双向链表与双哈希映射（freq_to_list和key_to_iter）并维护min_freq变量。

c++实现高性能lfu缓存淘汰机制核心算法 _ 频率链表与时间复杂度【源码】

LFU缓存为什么不能只靠`std::map`或`std::unordered_map`实现

因为LFU的核心约束是：相同访问频次的键必须按“最近最少使用”顺序淘汰，而频次本身又会动态变化。仅用哈希表能O(1)查键，但无法O(1)定位并移动某个频次下的最老节点——这需要双向链表支持快速插入/删除/提频。更关键的是，频次从1升到2、2升到3……时，必须把节点从一个频次链表移到下一个，且所有频次链表要能被快速访问。

所以标准容器组合不够用，必须手写两层结构：外层是频次到链表头的映射（freq_to_list），内层是每个频次对应的双向链表（带key、value、freq的节点）。频次最大值不用预设，按需创建链表即可。

std::unordered_map> 存频次→链表，保证O(1)跳转到某频次链表
std::unordered_map::iterator> 存key→迭代器，实现O(1)定位和擦除
每次get()或put()触发频次+1时，先从原频次链表删节点，再插入新频次链表头部（表示最新访问）
维护一个min_freq变量，记录当前所有有效键中的最小频次，用于evict()时快速定位淘汰链表

`min_freq`怎么维护才不会错？常见崩坏点在哪

很多人在put()新增键时直接设min_freq = 1，结果导致后续get()提升频次后，旧的min_freq指向已空链表，evict()失败或删错键。正确做法是：只有当min_freq对应链表变空，且下一次需要淘汰时，才递增min_freq；而新增键一定让min_freq = 1，但前提是这个键确实是当前唯一频次为1的键——更稳妥的是在每次evict()前检查freq_to_list[min_freq]是否为空，为空则min_freq++并重试，直到非空。

不要在get()里更新min_freq：频次升高不会让min_freq变大，只可能不变或失效
不要在put()覆盖旧键时重置min_freq：旧键频次可能仍是全局最小，覆盖只是修改值，不改变频次分布
evict()必须循环检查：while (freq_to_list[min_freq].empty()) min_freq++;，否则第一次min_freq卡死就永远淘汰不了
新增键（cache未满且key不存在）时，min_freq一定设为1，这是唯一直接赋值的时机

双向链表节点要不要存`freq`字段？为什么`std::list`不能省掉自定义结构

必须存。因为std::list里的Node结构体至少含key、value、freq三个字段。光靠链表位置推断频次是错的——不同频次链表是隔离的，同一链表内所有节点频次相同，但链表本身不携带频次元信息。如果节点不存freq，当需要把节点从freq=2链表移到freq=3链表时，你根本不知道它原来频次是多少，只能靠外部状态维护，极易出错。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

另外，std::list不能替换成std::vector或std::deque：前者删中间元素是O(n)，后者不支持O(1)迭代器失效防护（erase后其他迭代器可能失效），而std::list::iterator在插入/删除时不无效，正好满足我们用key_to_iter长期持有位置的需求。

节点定义示例：
```
struct Node { int key, value, freq; };
```
不能用std::list<:pair int>>代替：缺freq字段，无法支撑提频逻辑
避免在节点里存指针（如prev/next）：用std::list就别手动管理指针，否则增加内存和逻辑负担
key_to_iter映射的value类型必须是std::list::iterator，不是auto或void*，否则编译不过

时间复杂度真能稳定O(1)？哪些操作实际会退化

理论O(1)成立的前提是：哈希表查找平均O(1)，std::list的splice或erase+push_front是O(1)，且min_freq递增总次数受限于总操作数。但现实中，min_freq的while循环看似可能多跳几次，其实均摊仍是O(1)——因为每个频次链表最多被清空一次，总清空次数≤总put数。

真正容易退化的是哈希表冲突。如果大量key的std::hash（或自定义key的hash）发生碰撞，key_to_iter或freq_to_list的查找会变成O(桶长)。对整数key影响小，但对std::string key，务必提供良好哈希函数，或预留足够bucket数：key_to_iter.reserve(capacity)。

get()：查key_to_iter → 取迭代器 → 读值 → 删原链表节点 → 插入freq+1链表头部 → 更新key_to_iter → O(1)均摊
put()：若key存在，同get()后更新value；若不存在，检查容量→淘汰→插入freq=1链表→O(1)均摊
唯一隐式循环是evict()里的min_freq推进，但总推进步数≤总put数，均摊O(1)
别忘了std::list::erase(iterator)是O(1)，但std::list::remove(value)是O(n)，绝对不能用后者