LFU缓存不能只靠std::map或std::unordered_map实现，因其需在相同频次下按LRU顺序淘汰且频次变更时O(1)移动节点，必须结合双向链表与双哈希映射（freq_to_list和key_to_iter）并维护min_freq变量。
LFU缓存为什么不能只靠std::map或std::unordered_map实现
因为LFU的核心约束是：相同访问频次的键必须按“最近最少使用”顺序淘汰，而频次本身又会动态变化。仅用哈希表能O(1)查键，但无法O(1)定位并移动某个频次下的最老节点——这需要双向链表支持快速插入/删除/提频。更关键的是，频次从1升到2、2升到3……时，必须把节点从一个频次链表移到下一个，且所有频次链表要能被快速访问。
所以标准容器组合不够用，必须手写两层结构：外层是频次到链表头的映射（freq_to_list），内层是每个频次对应的双向链表（带key、value、freq的节点）。频次最大值不用预设，按需创建链表即可。
-
std::unordered_map<int std::list>></int>存频次→链表，保证O(1)跳转到某频次链表 -
std::unordered_map<int std::list>::iterator></int>存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></node>里的Node结构体至少含key、value、freq三个字段。光靠链表位置推断频次是错的——不同频次链表是隔离的，同一链表内所有节点频次相同，但链表本身不携带频次元信息。如果节点不存freq，当需要把节点从freq=2链表移到freq=3链表时，你根本不知道它原来频次是多少，只能靠外部状态维护，极易出错。
立即学习“C++免费学习笔记（深入）”；
另外，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>></:pair>代替：缺freq字段，无法支撑提频逻辑 - 避免在节点里存指针（如
prev/next）：用std::list就别手动管理指针，否则增加内存和逻辑负担 -
key_to_iter映射的value类型必须是std::list<node>::iterator</node>，不是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<int></int>（或自定义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)，绝对不能用后者
min_freq在evict()入口处的空链表跳过逻辑，以及新增key时无条件设min_freq = 1。这两处一错，整个LFU行为就不可控了。 
