std::unordered_map + std::list 无法真正实现 O(1) LFU 是因为查找最小频率需遍历频率桶，复杂度 O(F)；必须在每次频率变更时动态维护 minFreq，且仅在插入新 key 时重置为 1。
为什么 std::unordered_map + std::list 无法真正实现 O(1) LFU 查找最小频率
因为「查找当前最小频率」这个动作，在传统双哈希表+链表结构中仍是 O(F)，F 是不同频率的数量。即使 get 和 put 均摊 O(1)，只要每次 evict 前都要遍历所有频率桶找最小非空 freq，就破坏了整体 O(1) 保证。
真实瓶颈不在 key 定位，而在「哪个频率桶最冷」的动态判定。常见错误是维护一个 minFreq 变量但不严格更新——比如在某个 key 频率提升后，没检查该 freq 桶是否已空，导致 minFreq 滞后，后续驱逐时扫描空桶或跳过有效桶。
- 必须在每次
freq变更（尤其是递增）后，立即判断原 freq 桶是否变为空；若空且原 freq ==minFreq，则minFreq++ -
minFreq只能单调递增，不能回退——即使新 key 插入时 freq=1，也不重置为 1（除非整个缓存清空） - 插入新 key 时，
minFreq必须设为 1，这是唯一可重置的时机
如何用双向链表嵌套实现每个频率桶的 O(1) 头尾访问与删除
每个频率对应一个独立的 std::list（存 key），但仅靠 list 无法 O(1) 删除任意节点——因为 list::erase(iterator) 是 O(1)，但你得先拿到 iterator。所以必须额外用 std::unordered_map 存 key → 迭代器映射。
但注意：C++ 的 std::list 迭代器在被 erase 后立即失效，而你在 get 中要把 key 从旧 freq 桶移到新 freq 桶，需先 erase 再 splice 或 push_back。常见错误是先取 iterator、再 erase 旧桶、再用原 iterator 插入新桶——此时 iterator 已无效，UB。
- 正确做法：用
list.splice()移动节点，不销毁迭代器。例如freqLists[newFreq].splice(freqLists[newFreq].end(), freqLists[oldFreq], it) - 每个 freq 桶的 list 应使用
std::list而非std::vector，因后者移动元素会批量失效迭代器 - 避免在 list 中存储 value，只存 key；value 单独存在另一个
std::unordered_map（key → {value, freq}）>
LFU 缓存中 key 频率更新的三个关键触发点及对应操作
不是只有 get 才改 freq——put 命中已有 key 时也要更新 freq，且必须和 get 逻辑一致；而 put 未命中时，新 key 的 freq 初始化为 1，并重置 minFreq = 1。
最容易漏的是：当 put 触发淘汰时，被删的 key 若恰好是当前 minFreq 桶里最后一个，必须同步更新 minFreq。否则下次 get 或 put 仍会误判最小频率。
-
get(key)：查到则 freq++，从 oldFreq 桶移出，插入 newFreq 桶；若 oldFreq ==minFreq且桶空，则minFreq++ -
put(key, value)命中：同get更新 freq；未命中：插入 key=1 新桶，minFreq = 1；若缓存满，先按minFreq桶头节点淘汰，再检查该桶是否空，若是且minFreq未变，则minFreq++ - 所有对 freq 桶 list 的修改（push_front/push_back/splice/erase），都必须伴随对
minFreq的条件检查
C++ 实现中容易崩溃的三个内存与迭代器陷阱
高频操作下，迭代器失效和 map 插入顺序错乱是段错误主因。尤其在多线程未加锁前提下，但即使单线程，逻辑错误也会触发 assert 或静默 UB。
- 不要用
std::list::begin()作为“最久未用”节点——它只是插入顺序头，LFU 要求同频内按访问时间淘汰，所以必须用push_back()插入，用front()淘汰（即 FIFO within freq） - 在
put中淘汰 key 后，必须同时从keyToFreq、keyToValue、keyToIterator三个 map 中 erase，缺一不可；否则残留的keyToIterator指向已销毁节点，后续get会 crash -
std::unordered_map::erase(key)不会自动释放 value（如 list iterator），但std::list::erase(it)会调用 value 析构——若 value 是自定义类型，确保析构安全；内置类型无问题
真正难的不是写完，而是让 minFreq 在任意交错的 get/put/evict 序列下始终指向一个非空桶。这需要把「桶空」检测下沉到每一次桶变更的原子操作里，而不是集中到 evict 函数末尾统一扫一遍。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
