LFU缓存必须手写双向链表节点，因std::list+迭代器组合在频次迁移时会导致迭代器失效、隐式构造空链表、minFreq扫描退化为O(F)，且节点频次字段不可省略，minFreq需惰性校验并仅在evict前循环跳过空桶。
LFU 缓存必须手写双向链表节点，不能靠 std::list + 迭代器组合实现 O(1)；否则在频次迁移时会因迭代器失效、隐式 map 构造或遍历找 minFreq 导致崩溃或超时。
为什么 std::list + std::unordered_map::iterator> 会出问题
这不是写法“不优雅”，而是根本不可靠：
-
std::list::erase(iterator)要求 iterator 有效，但跨频次移动节点时需先从旧链表erase、再push_front到新链表——中间若发生异常或逻辑错位，iterator就 dangling 了 -
freq_to_list[minFreq]直接用operator[]会隐式构造空std::list，接着调.back()必然抛std::out_of_range -
std::map查频次桶是O(log F)，而 LFU 要求所有操作均摊O(1)；稀疏频次（如只有 1/5/100）会让 map 内部空桶堆积，minFreq扫描退化成O(F)
Node 结构里必须显式存 freq 字段
别试图省这个字段，也别靠“它在哪个链表里就等于哪个频次”来推断：
- 节点在
get()过程中处于“已删未插”状态，既不在freqMap[2]也不在freqMap[3]，此时唯一可信的频次来源是node->freq - 淘汰时要判断
old_freq == minFreq才触发minFreq++，这个比对依赖node->freq值，不是链表位置 - 高频压缩优化（如把所有
freq > MAX_FREQ归入同一桶）会让链表位置和真实频次彻底脱钩
minFreq 只能惰性校验，且只在 evict() 前检查
它不是“当前最小频次”的快照，而是“下一个可淘汰频次”的游标。更新时机极其有限：
- 新 key 插入时，无条件设
minFreq = 1（因为新节点必进freqMap[1]） -
get()或put()导致某频次链表清空，且该频次恰好等于minFreq，才执行minFreq++ -
evict()开始前必须用freqMap.find(minFreq)而非freqMap[minFreq]，并循环跳过空桶：
auto it = freqMap.find(minFreq);
while (it == freqMap.end() || it->second.empty()) {
minFreq++;
it = freqMap.find(minFreq);
if (minFreq > MAX_FREQ) { minFreq = 1; break; }
}
Node* victim = it->second.tail->prev;
手写双向链表节点比用 std::list 更稳、更省内存
标准库链表在 LFU 场景下是“过度设计”：
-
std::list每个节点额外带 allocator 控制块，cache 不友好；手写Node把prev/next直接嵌入结构体，连续布局，访问局部性好 - 迁移节点只需改指针：
remove_from_list(node)+insert_to_head(freqList, node)，无迭代器生命周期管理负担 - 配合
std::unordered_map查 key → node，和std::unordered_map查 freq → 链表，所有操作严格O(1)
最易被忽略的是：所有链表操作（插入、删除、移动）必须原子完成，中间不能暴露半截状态；minFreq 的更新永远滞后于实际链表变化，靠 evict() 入口那一次 while 循环兜底——这个“懒”不是偷懒，是唯一能兼顾正确性与性能的做法。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
