标准std::map或std::unordered_map无法实现LFU的O(1)频次更新，因其仅支持key→freq映射，无法O(1)定位key在频次链表中的位置；需结合std::list（保证迭代器稳定）与多层哈希索引（key→{freq,iter}、freq→list）来同步维护频次和位置，并动态更新minFreq。
为什么标准std::map或std::unordered_map无法直接实现O(1)频次更新
LFU要求每次get或put时，对应key的访问频次+1，且需在O(1)内完成「将该key从旧频次桶移到新频次桶」。单纯用std::unordered_map只能查频次，但无法快速定位该key在哪个频次对应的双向链表中——移除操作会退化为O(N)。
关键矛盾在于：频次更新必须同时修改两个维度的数据结构：一是key→freq映射，二是freq→key集合（且需支持快速插入/删除任意节点）。因此必须引入双向链表+哈希索引的组合结构。
- 每个频次对应一个
std::list（保持插入顺序，便于LRU式淘汰） - 用
std::unordered_map反向索引每个key在对应频次链表中的位置::iterator> - 再用
std::unordered_map存key的当前频次和迭代器，避免遍历查找::iterator>>
std::list迭代器为何能长期有效且支持O(1)擦除
std::list是双向链表，其迭代器在元素未被擦除前永不失效；插入/擦除节点不会影响其他节点的迭代器。这使得我们可以把std::list作为“句柄”长期保存在哈希表中，后续erase(iterator)就是真正O(1)。
对比std::vector或std::deque：任何插入/删除都会导致大量迭代器/指针失效，无法安全持有。
- 必须用
std::list，不能用std::forward_list（不支持双向遍历，无法做LRU层序淘汰） - 所有
erase调用都传入已缓存的迭代器，而非通过key查找后再删——后者是O(N)陷阱 - 移动key时：先用原频次迭代器
erase，再push_back到新频次链表，同时更新key的迭代器缓存
如何维护最小频次minFreq并保证O(1)获取待淘汰key
LFU淘汰的是当前最小频次中「最久未使用」的key（即对应链表头部）。但minFreq不是静态值：当某个频次链表变空时，minFreq必须立刻递增；而新插入key时，minFreq重置为1。难点在于「何时检测链表为空」。
- 每次
get或put导致某频次链表empty()后，立即检查if (freq == minFreq && list.empty()) minFreq++ -
put一个全新key时，minFreq = 1（不管之前是多少） - 淘汰只发生在
put且缓存满时：取freqLists[minFreq].front()，删掉它，再从三个哈希表中清除对应记录 - 注意：
minFreq可能跳变（如从3直接到5），所以不能假设它只+1
C++17下避免裸指针与内存泄漏的关键细节
整个结构完全基于栈对象和标准容器，无需new/delete。但容易忽略的是：当std::list::iterator指向的节点被erase后，该迭代器立即变为end()或无效状态，若之后误用会UB。
- 每次
erase后，立即将对应key在keyTable中的迭代器字段设为std::list（空迭代器），并在后续操作前判空::iterator{} - 使用
std::optional<:pair std::list>::iterator>>替代裸pair可显式表达“是否已初始化”，但会增加开销；更轻量的做法是用bool valid标记位 - 所有容器类型明确指定
Key和Value模板参数，避免ADL或隐式转换引发的哈希冲突（比如用std::string_view作key时，确保std::hash特化可用）
最易被忽略的一点：当多个key具有相同频次时，它们在链表中的相对顺序决定了淘汰优先级——这个顺序必须严格按访问时间升序排列（最早访问的在前），而push_back天然满足，但必须确保所有路径都走push_back，不能混用push_front。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
