LFU缓存不能仅用std::map或std::unordered_map实现，因其无法在频率相同时按访问时序O(1)淘汰最久未用项；需双层结构：外层哈希表O(1)定位节点，内层按频分组的双向链表维护同频时序，并辅以min_freq变量和Node中iter/list_ptr字段保障O(1)更新与删除。
LFU缓存为什么不能只用 std::map 或 std::unordered_map 单独实现
因为 LFU（Least Frequently Used）要求在频率相同时，淘汰「最近最久未使用」的项——但频率本身会动态变化，且同一频率下需维护访问时序。单纯哈希表无法表达“同频项的插入/访问先后关系”，而 std::map 按 key 排序，又不反映访问顺序。
常见错误是把频率当 key、value 当值集合，再用 std::list 存值——但这样无法 O(1) 定位某个 key 对应的节点（删除或更新频率时得遍历），命中率会因 get() 变成 O(n) 而断崖下跌。
正确做法是双层结构：
- 外层：
std::unordered_map<key node></key>，用于 O(1) 定位任意 key 对应的缓存节点 - 内层：按频率分组的双向链表（
std::list<node></node>或自定义链表），每组内节点按访问时间倒序（新访问的插在 front），保证同频下能 O(1) 淘汰 tail - 额外维护一个
std::unordered_map<int std::list>::iterator></int>记录每个频率对应的最小访问时间节点（即该频组的 tail），用于快速取待淘汰项
Node 结构体必须包含哪些字段才能支持 O(1) 频率提升
仅存 key、value、freq 不够。当某 key 被 get() 访问时，需把它从原频组链表中移出、插入到 freq+1 组的 front —— 这要求节点自带链表指针，且所属链表能反向定位其迭代器（否则 erase 代价为 O(n)）。
立即学习“C++免费学习笔记（深入）”；
所以 Node 至少含：
Key keyValue valueint freq-
std::list<node>::iterator iter</node>—— 指向它在当前频组链表中的位置（构造时由list.push_front()返回赋值） -
std::list<node>* list_ptr</node>—— 指向它当前归属的频组链表（避免每次都要查 map 找对应 list）
注意：iter 和 list_ptr 必须在每次移动节点时同步更新，漏掉任一就会导致后续 erase(iter) 崩溃或行为未定义。
如何避免 put() 时因频率升级引发的链表空悬与内存泄漏
典型坑：节点从 freq=2 的链表移到 freq=3 的链表后，没清空原链表里的迭代器，也没更新 list_ptr；下次再访问该节点，iter 已失效，erase() 触发 UB；或者旧链表残留节点指针，导致容量统计错误甚至 double-free。
安全写法是封装移动逻辑：
void move_to_next_freq(Node& node) {
// 1. 从原链表移除
node.list_ptr->erase(node.iter);
// 2. 更新 freq
node.freq++;
// 3. 插入新频组（若不存在则新建）
auto& new_list = freq_lists[node.freq];
node.iter = new_list.emplace(new_list.begin(), node);
node.list_ptr = &new_list;
}
关键点：
- 必须先
erase再emplace，不能反过来（否则iter仍指向旧位置） -
freq_lists是std::unordered_map<int std::list>></int>，按需创建，不用预分配所有频率 - 每次
put()若 key 已存在，调用move_to_next_freq()；若不存在，检查容量，必要时调用evict_lfu()
evict_lfu() 怎么找真正“最不常用”的项而不误删高频项
误区：遍历所有频率，取最小 freq 对应链表的 tail —— 错。因为最低频组可能刚被访问过（比如只有 1 个 item，刚 get() 过），而次低频组里有多个长期未访问的项，实际更该删后者。
LFU 标准定义是：先比频率，频率最小者候选；频率相同时，选其中「最久未使用」者（即该频组链表的 tail）。所以只需维护一个变量 min_freq，记录当前所有存活节点中的最小频率值。
更新时机很关键：
- 每次
put()新增节点时，min_freq = 1 - 每次
get()或put()导致某节点频率提升，且该节点是原频组唯一成员，则原频组变空 → 若min_freq == 原freq，需递增min_freq直到找到非空频组（最坏 O(F)，但 F 通常很小） -
evict_lfu()直接取freq_lists[min_freq].back()，删完后若该链表为空，同样要更新min_freq
这个 min_freq 是整个 LFU 正确性的锚点，漏更新或错更新，缓存行为就完全偏离 LFU 语义。
