不能直接用 std::list + std::unordered_map 实现 LFU/LRU 混合淘汰，因二者排序维度冲突：LRU 依赖访问时间，LFU 依赖频次，单链表无法同时维护两个有序性；必须为每个频次维护独立 LRU 链表（频次桶），并记录 min_freq，Node 需含 key、value、freq，哈希表存 key→list::iterator，更新频次时需从旧桶删除再插入新桶头部，淘汰时从 min_freq 桶尾部删除并维护 min_freq 正确性。
为什么不能直接用 std::list + std::unordered_map 实现混合淘汰
因为 LRU 和 LFU 的排序维度冲突：LRU 依赖访问时间（最新访问在前），LFU 依赖频次（高频在前）。单纯链表只能维护一个序，强行插入时会破坏另一个维度的局部性。比如按频率插入后，同一频率内的节点时间顺序就乱了；反之亦然。
常见错误是把 std::list 当成“双排序容器”来用，结果 get() 后频次+1，却只移动节点到新频次段头部，没保证该段内仍按 LRU 排序——这会导致同频次下最久未用的项反而被保留。
- 必须为每个频次维护独立的 LRU 链表（即“频次桶”）
- 需额外记录全局最小频次（
min_freq），避免每次淘汰都遍历所有桶找非空桶 -
std::unordered_map的 value 类型不能只存 value，必须包含freq和指向其所在链表节点的迭代器（list<node>::iterator</node>）
Node 结构体里必须带 key 字段
淘汰时要从链表尾部删节点，但仅靠 value 无法反查 key，也就无法从哈希表中同步删除映射。所以 Node 至少得有：key、value、freq。
有人尝试用 std::map<int list>>></int> 省掉 Node，但这样无法在 O(1) 内通过 value 定位到对应链表节点——因为 list::remove() 需迭代器，而 map 查 value 是 O(N)。
立即学习“C++免费学习笔记（深入）”；
- 正确做法：
struct Node { K key; V value; int freq; }; - 哈希表存：
unordered_map<k pair list>::iterator>></k>→ 不行，pair无法存freq - 应存：
unordered_map<k list>::iterator></k>，再配合外部结构体或封装类管理freq和桶映射
更新频次时如何保持同频次内 LRU 有序
关键不是“把节点移到新频次链表头”，而是“从旧频次链表中移除，再插入新频次链表头”。否则旧链表残留的迭代器会失效，且新链表头插后，同频次内访问顺序就丢失了。
具体步骤（以 get(key) 为例）：
- 从哈希表拿到
it = cache[key]（指向list<node>::iterator</node>） - 读出当前
it->freq，记为f - 从
freq_buckets[f]中erase(it) it->freq++- 将
it插入freq_buckets[f+1]头部（push_front） - 若
freq_buckets[f]变为空，且f == min_freq，则min_freq++
注意：list::erase(iterator) 不会使其他迭代器失效，但必须确保 it 确实属于 freq_buckets[f] —— 这要求每次插入/移动都严格更新桶引用。
淘汰策略触发时机与 min_freq 维护陷阱
不是每次 put() 溢出才淘汰，而是当 size() > capacity 且新 key 不存在时，才触发淘汰。此时必须从 freq_buckets[min_freq] 尾部删节点。
容易错的地方：
-
min_freq初始值设为 0，但首次插入后应为 1；更稳妥是初始化为 1，第一次put后显式设min_freq = 1 - 淘汰后如果
freq_buckets[min_freq]变空，要循环min_freq++直到非空或越界 —— 但实际只需检查一次，因为只有刚删完的那个频次可能为空，其他频次不会因本次操作变空 - 如果
put是更新已有 key（key 存在），不触发淘汰，但要更新频次和位置；如果是新 key，先淘汰再插入，且新节点freq = 1，插入freq_buckets[1]头部，并重置min_freq = 1
真正复杂的是多线程场景下的 min_freq 竞态：一个线程刚删完 min_freq 桶，另一个线程 get 升频导致该桶再次非空，但 min_freq 已被跳过。单线程实现可忽略，但生产环境必须加锁或改用无锁计数器。
