std::unordered_map + std::list 组合在 lfu 中退化为 o(n) 是因无法 o(1) 定位最小非空频率桶，需遍历查找；必须用 std::map 管理 freq→list 映射，利用 begin()->first 获取当前最小频次，删空桶后立即 erase 以保证 minfreq 始终有效。
为什么 std::unordered_map + std::list 组合在 LFU 中会退化成 O(n) 查最小频率
因为标准容器不支持按频率快速定位——每次 get() 或 put() 后需遍历所有频率桶找最小非空桶，最坏触发全量扫描。真实高频写入场景下，minFreq 变量必须维护，但仅靠它还不够：你得保证「删掉某个频率桶后，它真能被立刻跳过」。
关键矛盾在于：minFreq 更新不能滞后于实际桶状态。比如频率为 2 的桶刚清空，但 minFreq 还是 2，下次插入就得从 2 开始线性找下一个有节点的桶。
- 必须用一个单独的
std::map<int std::list>></int>存频率桶（有序，天然升序迭代） -
minFreq不手动更新，而是每次需要时调用freqMap.begin()->first—— 因为std::map删除空桶后，begin()自动指向当前最小非空频率 - 删除节点时，若其所在桶变空，立即调用
freqMap.erase(freq)，这是 O(log F) 但换来后续minFreq查询 O(1)
Node 结构体里到底要不要存 freq 字段
要，而且必须存。LFU 的核心是「同频率节点间按访问时序淘汰」，所以每个节点得知道自己属于哪个频率桶；同时，get() 操作要把它从旧桶移到新桶（freq+1），没 freq 字段就无法反查原桶位置。
常见错误是只靠 key 在哈希表中映射到节点指针，却忘了节点自己不携带频率信息，导致移动时无法定位源桶。
-
Node至少含：int key,int value,int freq,std::list<node>::iterator it_in_list</node>（用于 O(1) 从 list 中 erase） - 别用裸指针管理 list 迭代器——
std::list迭代器在 insert/erase 时不失效，但 relocate 节点必须显式erase+push_front，并更新it_in_list - 不要把
freq存在哈希表 value 里再冗余一份——增加同步风险，且无性能收益
put() 中「容量满时淘汰」怎么避免重复查找 minFreq 桶
不是先取 minFreq，再查桶，再删尾节点；而是直接取 freqMap[minFreq].back()，删完立刻检查该桶是否为空，空则 freqMap.erase(minFreq)。整个过程只查一次桶、只删一个节点。
注意：必须用 back() 而非 front()，因为同频节点按 LRU 管理（最近访问放 front），最久未用在 back —— 这是 LFU-LRU 混合策略的关键约定。
- 淘汰前确保
freqMap非空：if (freqMap.empty()) return; -
minFreq = freqMap.begin()->first必须在淘汰前重读，防止并发或逻辑错位 - 删节点后，从哈希表中
cache.erase(node.key)，再从freqMap[minFreq].pop_back()，顺序不能反，否则迭代器悬空 - 如果用
std::list::splice()移动节点，可避免拷贝，但需确保目标桶已存在，否则先freqMap.emplace(freq, std::list<node>{})</node>
std::map 和 std::unordered_map 在 freqMap 中能互换吗
不能。这里必须用 std::map，不是因为「要排序」，而是因为 begin() 是唯一能 O(1) 拿到最小键的方式；std::unordered_map 不提供有序遍历接口，你要找最小频率只能 std::min_element，O(F)。
虽然 std::map 插入/删除是 O(log F)，但 F（不同频率数）远小于总节点数 N —— 实测中 F 通常 ≤ log₂(N)，所以 log F ≈ 5~7，基本可视为常数。
- 别为了理论上的 O(1) 哈希强行套
unordered_map+ 手动维护堆或 set —— 增加复杂度且易出错 - 如果真遇到极端场景（F > 10⁵），才考虑用
std::priority_queue+ 延迟删除，但此时缓存设计本身可能已偏离 LFU 原意 -
freqMap的 key 是频率值，value 是对应节点链表，别把 key 设成 string 或复合类型，徒增开销
真正卡性能的从来不是 map 查 minFreq，而是频繁的 list splice 和哈希表 rehash。控制好初始 cache 容量、预分配 freqMap 桶数量，比纠结容器类型重要得多。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
