C++ 实现高性能 LFU 缓存淘汰机制最小频率查找寻址优化算法

std::unordered_map + std::list 组合做 LFU 容易超时，因未在同频链表内维护访问时序，导致 get/put 时需遍历找最久未用项，退化为 O(n)；正确做法是用双向链表按频次分桶且桶内按访问时间排序，并辅以 freq_to_list、key_to_node 和 min_freq 三者协同实现严格 O(1)。

c++ 实现高性能 lfu 缓存淘汰机制最小频率查找寻址优化算法 _ 源码【源码】

为什么 std::unordered_map + std::list 组合做 LFU 容易超时

LFU 的核心难点不在“计数”，而在“相同频率下快速找到最久未用的项”——即当多个 key 频次相同时，必须 O(1) 拿到最老的那个。用 std::unordered_map 存 key→freq，再用 std::list 按 freq 分桶，但若每个 freq 对应一个 list，且不维护每层的 LRU 顺序，get() 或 put() 时仍需遍历 list 找 tail，退化为 O(n)。

常见错误是只按 freq 分桶，却没把“同频内的访问时间序”固化进结构里。正确做法是：每个 freq 对应一个双向链表（或 list），且该链表本身按访问时间从头到尾排列；同时用一个 map 记录每个 freq 对应的链表头节点（或迭代器），避免每次查最小 freq 都要扫描所有非空桶。

必须用双向链表（如 std::list）而非 vector，保证插入/删除 O(1)
不能只存 freq → list<key></key>，还要额外维护 min_freq 变量，并在 put() 插入新 key 或 get() 提升 freq 时动态更新它
min_freq 更新不是简单取 min，而是“当前最小 freq 对应的 list 是否为空”——为空则 ++min_freq，否则保持

如何用两个 map + 一个 list 实现真正 O(1) 的 LFU

关键结构是：key_to_node（unordered_map<int list>::iterator></int>）、freq_to_list（unordered_map<int list>></int>）、min_freq（int）。其中 Node 是自定义结构，含 key、val、freq。

每次 get(key)：先从 key_to_node 查到对应 node 迭代器 → 读值 → 从 freq_to_list[node->freq] 中 erase 该 node → 将 node.freq++ 后 push_back 到 freq_to_list[node->freq] → 更新 key_to_node[key] 指向新位置 → 若原 freq == min_freq 且对应 list 空了，则 min_freq++。

put(key, value) 时若已存在，复用 get() 逻辑后仅更新 val；若不存在，检查容量：满则从 freq_to_list[min_freq] 的 front 弹出（即最久未用的同频项），并从 key_to_node 删除对应 key
新 key 的初始 freq=1，直接 push_back 到 freq_to_list[1]，并重置 min_freq = 1
所有操作都不涉及循环遍历 freq 表，min_freq 始终有效，所以淘汰是严格 O(1)

std::list 迭代器失效陷阱与 safe erase 写法

std::list 迭代器只有在被 erase 的元素上才失效，其他迭代器均有效——这是它比 vector 或 unordered_map 更适合本场景的关键。但新手常犯错：在 erase 前没保存 next 迭代器，或误用 post-increment 导致二次 erase。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

安全写法示例（在 freq_to_list[f].erase(it) 后，it 已失效，不能再用）：

auto next_it = std::next(it); // 先存
freq_to_list[f].erase(it);
// it 不可再用，但 next_it 仍有效（只要没被删）

不要写 freq_to_list[f].erase(it++)：这会先拷贝再 increment，但 erase 后原 it 已无效，increment 行为未定义
不要在 erase 后继续用 it->key 或类似访问：UB（undefined behavior）
如果只是单点删除（如淘汰 head），直接 freq_to_list[min_freq].pop_front() 更安全，无需迭代器管理

为什么不用 std::map 替代 unordered_map

表面上看，std::map 能天然按 freq 排序，似乎方便找最小 freq ——但实际得不偿失。因为 LFU 中 freq 变化集中于 ±1，且绝大多数操作只访问当前 key 的 freq 和 min_freq 对应的 bucket，不需要遍历或范围查询。

用 std::map 带来两个硬伤：

每次 freq_to_list[f] 访问都是 O(log F)，F 是不同 freq 的数量（可能达 O(n)），而 unordered_map 是均摊 O(1)
min_freq 本可通过变量维护，用 map 反而让逻辑变重：你仍需检查 map.begin()->first 是否有效，且 erase 空 bucket 时还要调用 map.erase(f)，增加分支和异常路径
实测在 10⁵ 操作量级下，unordered_map 版本比 map 快 2–3 倍，尤其在高冲突或 rehash 场景下更稳定