直接用 std::map + std::list 实现 lfu 易超时，因无法 o(1) 完成“按频率分组+组内 lru 排序”；瓶颈在于缺乏快速定位最低非空频率的能力，且同频节点未分链表导致 evict 时需遍历——最坏 o(n)。
为什么直接用 std::map + std::list 实现 LFU 容易超时
因为标准容器组合无法在 O(1) 时间内完成「按频率分组 + 组内按访问时间排序」的双重调度。每次 get() 或 put() 都可能触发频率提升、节点迁移、最低频组清空等操作，若用 std::map<int std::list>></int> 存频率到链表映射，再用额外哈希表存 key→Node*，仍需遍历最低频链表找待删节点——最坏 O(n)。
关键瓶颈在于：没有快速定位「当前最低非空频率」的能力，也没有让同频节点按 LRU 顺序自然淘汰的结构支撑。
- 避免在
evict()时扫描所有频率桶找最小非空 freq —— 改用变量min_freq动态维护 - 不要把「同频节点」塞进一个扁平
std::list—— 每个频率单独维护双向链表，且链表头尾即最近/最远访问 - 不能只靠
key → Node*查找；Node 必须自带freq和双向指针，并在插入/提升时同步更新所在链表和min_freq
Node 结构体必须包含哪些字段才能支撑 O(1) 操作
它不是普通缓存节点，而是频率链表网络里的“活连接点”。少了任一字段，都会导致某类操作退化。
-
int key, value：基础数据 -
int freq：当前访问频率，决定它属于哪个频率链表 -
Node* prev, *next：用于在所属频率链表中快速插入/删除（O(1)） -
std::unordered_map<int node>::iterator map_iter</int>：保存其在全局cache_map中的迭代器，确保erase()不需要查找
注意：Node 不需要存“所属频率链表指针”，因为链表由外部 std::unordered_map<int listhead></int> 管理，Node 只负责在链表内部连通。
如何用两个哈希表协同管理频率链表与节点映射
核心是分离关注点：一个管「频率→链表」，一个管「key→节点」，两者通过 Node 的 freq 和 map_iter 字段联动。
-
std::unordered_map<int listhead> freq_lists</int>：key 是频率值，value 是该频率下双向链表的头尾哨兵（推荐封装为ListHead{Node* head, *tail}） -
std::unordered_map<int node> cache_map</int>：key 是缓存 key，value 是指向堆上Node的裸指针（或unique_ptr，但要注意移动语义） - 每次
get(key)命中后，先从cache_map取出Node*，再根据其freq找到对应链表，将节点从原链表摘下、freq++、插入freq+1链表头部；同时检查原链表是否变空，若空且min_freq == old_freq，则min_freq++ -
put(key, value)若已存在，复用上述提升逻辑；若不存在且满容，则从freq_lists[min_freq]的尾部删节点，并从cache_map中擦除对应项
为什么 min_freq 更新必须严格依赖链表空状态而非计数器
用独立计数器（如 freq_count[freq]++）记录各频次节点数，看似可行，但会在并发或异常路径下失准——比如节点未成功插入新链表就抛异常，计数器已加却未减，min_freq 就永远卡住。
- 只在节点从某频率链表移出后，立即检查该链表是否为空（
head->next == tail） - 仅当
min_freq对应链表为空时，才执行min_freq++，并继续检查下一个频率，直到找到首个非空链表（通常只需一次） - 插入新节点时，若
freq == 1，则重置min_freq = 1（因为新 key 总带来频率 1，它必然是当前最小可能值）
这个逻辑看似多一步判断，却是唯一能保证 min_freq 始终有效的办法。漏掉链表空检测，缓存就会在满载后拒绝写入或误删高频项。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
