C++实现带频率权重的LFU缓存算法模型 _ 数据结构设计与命中率【源码】-C++-PHP中文网

LFU缓存不能仅用std::map或std::unordered_map实现，因其无法在频率相同时按访问时序O(1)淘汰最久未用项；需双层结构：外层哈希表O(1)定位节点，内层按频分组的双向链表维护同频时序，并辅以min_freq变量和Node中iter/list_ptr字段保障O(1)更新与删除。

c++实现带频率权重的lfu缓存算法模型 _ 数据结构设计与命中率【源码】

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，用于 O(1) 定位任意 key 对应的缓存节点
内层：按频率分组的双向链表（std::list 或自定义链表），每组内节点按访问时间倒序（新访问的插在 front），保证同频下能 O(1) 淘汰 tail
额外维护一个 std::unordered_map::iterator> 记录每个频率对应的最小访问时间节点（即该频组的 tail），用于快速取待淘汰项

`Node` 结构体必须包含哪些字段才能支持 O(1) 频率提升

仅存 key、value、freq 不够。当某 key 被 get() 访问时，需把它从原频组链表中移出、插入到 freq+1 组的 front —— 这要求节点自带链表指针，且所属链表能反向定位其迭代器（否则 erase 代价为 O(n)）。

所以 Node 至少含：

Key key
Value value
int freq
std::list::iterator iter —— 指向它在当前频组链表中的位置（构造时由 list.push_front() 返回赋值）
std::list* list_ptr —— 指向它当前归属的频组链表（避免每次都要查 map 找对应 list）

注意：iter 和 list_ptr 必须在每次移动节点时同步更新，漏掉任一就会导致后续 erase(iter) 崩溃或行为未定义。

如何避免 `put()` 时因频率升级引发的链表空悬与内存泄漏

典型坑：节点从 freq=2 的链表移到 freq=3 的链表后，没清空原链表里的迭代器，也没更新 list_ptr；下次再访问该节点，iter 已失效，erase() 触发 UB；或者旧链表残留节点指针，导致容量统计错误甚至 double-free。

C++14

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

下载

安全写法是封装移动逻辑：

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>，按需创建，不用预分配所有频率
每次 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