c++高性能lfu缓存需用频次桶双向链表+哈希表实现o(1)操作：freqnode管理同频节点，freqmap映射频次到链表，minfreq记录最小频次；node含key/value/freq及迭代器it，cachemap实现键值o(1)查找与删除；put时升频或淘汰minfreq首节点，get时访问即升频并更新minfreq。

实现C++高性能LFU缓存需解决最小频率节点的O(1)定位问题——传统遍历查找minFreq会退化为O(n)，必须用双向链表+哈希表协同维护频次桶，使get/put操作严格维持在平均O(1)时间复杂度内。

构建频次桶双向链表结构

定义FreqNode结构体，包含freq值、指向同频次首尾节点的指针；用unordered_map*> freqMap映射频次到对应链表；用int minFreq记录当前全局最小频次，初始设为1。

每次新插入节点时，若该频次链表不存在，则新建list并插入freqMap；【minFreq必须在put首次插入时同步初始化为1，否则后续get操作无法正确更新】。

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

Node节点与缓存键值对的双向绑定

每个缓存项封装为Node结构：含key、value、freq三字段，并携带指向其所在freq链表中位置的list::iterator it。

用unordered_map cacheMap存储key→Node映射，确保O(1)键查找；同时在Node中保存迭代器，使得后续删除该节点时可直接通过it完成O(1)链表擦除。

put操作：频率升级与淘汰触发

方法一：键已存在
① 从cacheMap取出对应Node；
② 将其freq加1，从原freq链表中erase(it)，再push_back到freq+1链表末尾；
③ 更新cacheMap中该Node的it为新位置迭代器；
④ 若原freq链表变为空且minFreq等于该freq，则minFreq++（需检查freq+1链表是否存在，不存在则继续+1直到找到非空链表）。

方法二：键不存在且缓存满
第一步：定位minFreq对应链表的front节点，获取其key；
第二步：从cacheMap中erase该key；
第三步：从freqMap[minFreq]链表中pop_front；
第四步：若链表为空，从freqMap中erase(minFreq)条目；
第五步：插入新Node到freqMap[1]链表尾部，更新cacheMap，并重置minFreq = 1。

get操作：访问即升频与链表迁移

若key不在cacheMap中，直接返回-1；否则取出Node，freq++，将其从当前freq链表中移出，插入freq+1链表尾部；更新Node中的it和cacheMap值；【注意：若原freq等于minFreq且该链表被清空，必须立即更新minFreq，否则下次put淘汰会选错桶】。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！