lfu缓存不能仅用std::map或std::unordered_map实现，因其需按频次分组并o(1)移动节点，必须结合哈希表（快速查key）与按频次组织的双向链表（支持o(1)增频迁移和同频lru淘汰），且cachenode需内嵌freq和iter字段以保障操作原子性。
LFU 缓存为什么不能只用 std::map 或 std::unordered_map 单独实现？
因为 LFU 的核心是「按访问频次分组淘汰」，而频次会动态变化——每次 get() 或 put() 都可能让某个 key 的频次 +1，进而需要把它从旧频次链表挪到新频次链表。单纯哈希表能 O(1) 查 key，但无法 O(1) 定位并移动一个节点到另一条链表中。
所以必须拆成两层结构：std::unordered_map 存 key → 节点指针（快速查找），再配合一组双向链表（按频次组织，每个频次对应一条 LRU 风格链表）。
- 每条链表内节点按「最近使用」排序，保证同频次下淘汰最久未用的
- 新增频次时，不预分配所有频次链表，而是按需创建（比如首次出现 freq=1，才新建 freq=1 的链表）
- 维护一个最小频次
minFreq，用于 O(1) 找到当前可淘汰的链表头；put()淘汰时直接取freqList[minFreq]的尾节点
CacheNode 结构体里必须带哪些字段？
不是只存 key 和 value 就够了。LFU 移动节点时要改频次、改前后指针、还要知道它当前在哪条链表上——所以必须显式记录 freq 和所属链表的迭代器位置（或指针）。
常见错误是把 freq 放在外部映射里（比如 freqMap[key] = 3），这样每次移动节点还得查两次哈希表（一次找 node，一次找 freq），破坏 O(1) 假设。
- 正确字段：
int key,int value,int freq,list<cachenode>::iterator iter</cachenode>（指向它在链表中的位置） - 注意：不能存
list::iterator到自身链表（会循环依赖），所以实际用list<cachenode></cachenode>存指针，iter是该指针在 list 中的位置 - 构造时必须同步更新
iter，否则后续erase(iter)会崩溃
如何安全地更新节点频次并移动到新链表？
关键不是“加 1”，而是“从旧链表删掉，再插入新链表头部”。这一步容易漏掉三件事：更新 node->freq、修正 node->iter、检查并更新 minFreq。
典型错误现象：get(key) 后频次没变、或 minFreq 滞后导致提前淘汰高频 key。
- 先用
keyToNode.at(key)拿到 node 指针 - 从
freqList[node->freq]中erase(node->iter) -
node->freq++，然后 push_front 到freqList[node->freq]，并用begin()更新node->iter - 如果
freqList[minFreq].empty()，说明旧 minFreq 已无节点，minFreq++
C++17 下用 std::list + std::unordered_map 实现的最小可行代码片段
下面这段不是完整类，而是最关键的移动逻辑和初始化示意，去掉异常处理和封装，直击数据流转：
// 成员变量： std::unordered_map<int cachenode> keyToNode; std::unordered_map<int std::list>> freqList; int capacity; int minFreq = 0; <p>// get() 中频次更新部分： auto it = keyToNode.find(key); if (it == keyToNode.end()) return -1; CacheNode* node = it->second;</p> <p>// 从旧链表移除 freqList[node->freq].erase(node->iter);</p> <p>// 频次+1，插入新链表头部 node->freq++; freqList[node->freq].push_front(node); node->iter = freqList[node->freq].begin();</p> <p>// 更新 minFreq（仅当旧链表空且旧 freq == minFreq） if (freqList[minFreq].empty()) minFreq++; </p></int></int>
注意：这里 freqList 是 unordered_map<int list>></int>，不是数组——频次可能稀疏（比如只有 freq=1 和 freq=5），用 map 更省空间；但若频次范围极小且密集，改用 vector 也可，不过得预估最大频次。
真正难调试的点往往不在主干逻辑，而在 put() 中「容量满时淘汰」与「新 key 插入」的边界：比如新 key 频次为 1，但此时 minFreq 是 2，那淘汰完后 minFreq 应重置为 1——这个细节很多实现会忽略。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
