O(1) LFU需Node含key、value、freq及对应链表的iterator字段；minFreq须随链表空置实时更新；易错点包括遗漏旧节点删除、splice误用erase、minFreq更新时机错误。
为什么标准std::unordered_map + std::list组合做不到O(1) LFU？
因为LFU需要按频次分组、同频次内按访问时序淘汰，而单纯用std::list维护访问顺序时，提升某节点频次需先从链表中删除再插入到新频次对应链表——这要求能在O(1)定位并移除任意节点。但std::list::remove(value)是O(n)，std::list::erase(iterator)虽是O(1)，却无法在不遍历前提取到目标节点的iterator。
关键卡点在于：缓存项被再次访问时，必须立即把它从当前频次链表挪到freq+1链表头部，且不能遍历查找。
- 解决办法是为每个缓存项额外保存其在所属链表中的
std::list::iterator，存进哈希表里 - 同时维护一个频次到链表的映射：
std::unordered_map<int std::list>></int> - 还要记录当前最小频次
minFreq，用于O(1)定位待淘汰节点所在链表
Node结构体必须包含哪些字段才能支撑O(1)操作？
只存key、value、freq不够。缺少对链表位置的反向引用，会导致频次更新时无法快速摘除节点。
正确设计如下：
立即学习“C++免费学习笔记（深入）”；
struct Node {
int key;
int value;
int freq;
std::list<Node>::iterator it; // 指向自己在freq链表中的位置（关键！）
};
注意：it字段不是指针，而是std::list迭代器；它必须在节点插入链表后立刻赋值，并在节点被移出链表前失效——所以每次splice或erase后都要重置或不再使用。
-
freq初始为1，每次get或put命中时+1 -
it在插入到freq对应链表后，通过++list.begin()或list.emplace_front(...)返回的迭代器赋值 - 不要在
Node里存std::list<node>*</node>，那会引入裸指针管理和生命周期风险
如何维护minFreq且保证始终有效？
minFreq不是简单取所有频次的最小值——当某个频次的链表变空时，minFreq必须立刻推进到下一个非空频次，否则put触发淘汰时会尝试从空链表back()取节点，导致崩溃或未定义行为。
做法是：仅在get或put命中导致某节点freq提升时检查原频次链表是否变空；而put新增节点时，minFreq一定重置为1。
- 淘汰逻辑触发时，从
freqMap[minFreq].back()取待删节点，删完立刻检查freqMap[minFreq].empty() - 若为空，则
minFreq++，继续检查，直到freqMap[minFreq]非空或越界（此时说明缓存刚清空，后续操作会重建） - 不要用
std::map按频次排序来替代minFreq变量——那会让get和put退化为O(log F)，F为不同频次数量
实际编码时最容易踩的三个坑
这三个问题不报编译错误，但会导致缓存行为异常、内存泄漏或崩溃：
- 忘记在
put覆盖旧key时，先用旧Node.freq找到对应链表，调用erase(Node.it)——否则旧节点残留，新节点重复插入，size统计失准 -
std::list::splice移动节点时传错参数：应使用target_list.splice(target_list.begin(), source_list, node.it)，而不是source_list.erase(node.it)后再emplace，后者破坏了迭代器有效性 -
minFreq更新时机错误：比如在get中只更新频次却没检查原链表是否为空，导致后续淘汰从空链表取节点；或者在put新增节点后没把minFreq设为1
真正稳定的O(1) LFU实现，核心不在数据结构多炫酷，而在每个节点的iterator生命周期管理是否严密、minFreq是否与链表状态实时同步——这两处松动，整个O(1)承诺就塌了。
