c++怎么实现LRU与LFU缓存淘汰算法_c++ 频率统计与双向链表结合【案例】

---

LRU用std::list+std::unordered_map实现，通过链表维护访问时序（最新在头、淘汰尾部），map存key到链表迭代器的映射，确保get/put均为O(1)；LFU需按频次分桶，每桶内LRU管理，辅以minFreq优化淘汰；不用std::map因其实现为红黑树，查找O(log n)，不满足缓存高频O(1)要求。

LRU 用 std::list + std::unordered_map 实现最简可靠版本

核心是维护「访问时序」：最新访问的放链表头，淘汰时删尾部。不能只靠 map 记 key-value，必须用双向链表快速移动节点位置。

• std::list<:pair int>> 存 {key, value}，支持 O(1) 删除任意节点和 push_front
• std::unordered_map>::iterator> 快速定位 key 对应的链表迭代器
• 每次 get()：查 map → 找到则从 list 中 erase 原位置，再 push_front()，更新 map 中迭代器
• 每次 put()：若 key 已存在，同上更新；否则检查容量，满则先 pop_back() 并删 map 中对应 key，再插入新节点

class LRUCache {
    int cap;
    std::list> cache;
    std::unordered_map>::iterator> map;
public:
    LRUCache(int capacity) : cap(capacity) {}
    int get(int key) {
        if (map.find(key) == map.end()) return -1;
        auto it = map[key];
        int val = it->second;
        cache.erase(it);
        cache.push_front({key, val});
        map[key] = cache.begin();
        return val;
    }
    void put(int key, int value) {
        if (map.find(key) != map.end()) {
            cache.erase(map[key]);
        } else if (cache.size() >= cap) {
            auto last = cache.back();
            map.erase(last.first);
            cache.pop_back();
        }
        cache.push_front({key, value});
        map[key] = cache.begin();
    }
};

LFU 需要频率分组 + 双向链表嵌套，std::unordered_map 套 std::list 是关键结构

LFU 淘汰最低频且最久未用的项，光记 frequency 不够 —— 同频次下还得有访问时序。所以得按 freq 分桶，每桶内用 LRU 方式管理（即链表），再用 map 索引每个 key 所在的桶和节点。

• 外层：std::unordered_map>，key 是 frequency，value 是该频次下所有 Node{key, value, freq} 的链表
• 中间：std::unordered_map::iterator, int>>，记录 key → {所在链表迭代器, 当前 freq}
• 还需一个 int minFreq，用于 O(1) 找到待淘汰桶（避免遍历所有 freq）
• get()：查 key → 得到 oldFreq；从 oldFreq 桶中删除节点；插入到 oldFreq + 1 桶头；若 oldFreq 桶空且等于 minFreq，则 minFreq++
• put()：若 key 存在，同 get() 更新；否则新建 Node 插入 freq=1 桶，minFreq = 1；若超容，删 minFreq 桶尾节点

为什么不用 std::map 替代 std::unordered_map？性能差在哪

std::map 是红黑树，O(log n) 查找；而缓存操作要求 O(1) 定位，尤其在高并发或高频调用场景下，log n 会明显拖慢吞吐。实测百万次 get()，unordered_map 比 map 快 3–5 倍。

• 除非你需要按 key 排序（LFU/LRU 都不需要），否则无理由选 std::map
• unordered_map 的哈希冲突在负载因子 .reserve(n) 避免 rehash
• 注意自定义 key 类型需提供 hash 和 ==，内置类型如 int、string 已内置

容易被忽略的边界：迭代器失效与 list::splice() 的正确用法

直接 erase() 再 push_front() 看似自然，但对 list 迭代器来说，erase 后原迭代器立即失效 —— 而 map 里还存着它，下次访问就 UB。正确做法是用 splice() 移动节点，不破坏迭代器有效性。

立即学习“C++免费学习笔记（深入）”；

• 错误写法：cache.erase(it); cache.push_front(...); map[key] = cache.begin(); → it 已失效，但 map 未清，后续可能解引用野指针
• 正确写法（LRU）：cache.splice(cache.begin(), cache, it); map[key] = cache.begin(); → splice 是移动，it 仍有效
• LFU 中跨桶移动也必须用 splice，否则旧桶 erase 后，map 中保存的迭代器指向已销毁内存

实际写 LFU 时，minFreq 的维护和空桶清理最容易漏；哪怕只少一行 if (buckets[oldFreq].empty()) minFreq = std::min(minFreq, oldFreq + 1);，都会导致后续淘汰错对象。

# node  # ai  # c++  # 为什么  # red  # String  # if  # int  # 指针  # map  # 并发  # 对象  # 算法  # 链表  # 迭代  # 红黑  # 都不  # 遍历  # 均为  # 自定义  # 还得  # 再用  # 但对 

相关栏目： 【 Google疑问12 】 【 Facebook疑问10 】 【 网络优化76771 】 【 技术知识130152 】 【 IDC云计算60162 】 【 营销推广131313 】 【 AI优化88182 】 【 百度推广37138 】 【 网站推荐60173 】 【 精选阅读31334 】

相关推荐： Python如何创建带属性的XML节点  如何使用 Selenium 正确获取篮球参考网站球员名单元素列表  c++怎么用jemalloc c++替换默认内存分配器【性能】  mac怎么安装字体_MAC添加第三方字体与字体册管理【教程】  php怎么连接数据库_MySQL数据库连接的基础代码编写【说明】  Win10如何更改任务栏高度_Windows10解锁任务栏调整大小  Python迭代器生成器进阶教程_节省内存与懒加载实战  c++如何实现多态性_c++ 虚函数表原理与动态绑定机制【教程】  Windows系统时间服务错误_W32Time服务修复与同步教学  如何在 Go 中正确测试带 Cookie 的 HTTP 请求  如何高效获取循环末次生成的 NumPy 数组最后一个元素（无需额外循环）  Win11视频默认播放器怎么改_Win11关联第三方播放器【步骤】  如何使用Golang理解结构体指针方法接收者_Golang修改字段实践  Win11怎么查看wifi信号强度_检测Windows 11无线网络质量方法【详解】  mac怎么安装adb_MAC配置Android ADB开发环境【详解】  php怎么捕获异常_trycatch结构处理运行时错误的技巧【方法】  Windows蓝屏错误0x0000001E怎么修复_KMODEEXCEPTIONNOTHANDLED排查  php打包exe如何加密代码_防反编译保护方法【技巧】  Win11怎么关闭定位服务 Win11禁止应用获取位置信息【隐私】  Python变量绑定机制_引用模型解析【教程】  如何使用Golang管理模块版本_Golanggo mod tidy与升级方法  Windows电脑如何截屏？（四种快捷方法）  c# 在高并发下使用反射发射（Reflection.Emit）的性能  Win11怎么关闭透明效果_Windows11辅助功能视觉效果设置  Win11怎么清理C盘OneDrive缓存_Win11清理OneDrive缓存技巧【方法】  Win11怎么关闭右下角弹窗_Win11拦截系统通知广告【设置】  Mac如何使用听写功能_Mac语音输入打字【效率技巧】  Django 测试数据库表缺失与字段未创建问题的完整解决方案  Mac怎么查看活动监视器_理解Mac进程和资源占用【指南】  如何使用Golang指针与接口结合_实现方法调用和动态类型  如何使用Golang捕获并记录协程panic_保证主程序稳定运行  Windows10系统怎么查看显卡驱动_Win10设备管理器驱动更新  Python函数缓存机制_lru_cache解析【指导】  php转mp4怎么保留字幕_php处理带字幕视频转换说明【说明】  Win11怎么关闭自动调节亮度_Windows11禁用内容自适应亮度  Windows10系统怎么查看显卡型号_Win10 dxdiag显示选项卡  C++如何使用std::optional？（处理可选值）  php订单日志怎么导出excel_php导出订单日志到表格教程【教程】  c++的位运算怎么用 与、或、异或、移位操作详解【底层知识】  Windows10蓝屏代码DPC_WATCHDOG_VIOLATION_Win10死机修复指南  Win11任务栏怎么调到左边_Win11开始菜单居左设置教程【步骤】  Win11怎样激活系统密钥_Win11系统密钥激活步骤【攻略】  PHP 中如何在函数内持久化修改引用变量的指向  PHP中require语句后直接调用返回对象方法的语法解析  Win11如何设置电源计划_Win11电源计划优化教程【攻略】  C++如何解析JSON数据？（nlohmann/json库示例）  Windows10如何更改盘符名称_Win10重命名硬盘分区卷标  windows系统如何安装cab更新补丁_windows手动安装更新包教程  MAC怎么一键隐藏桌面所有图标_MAC极简模式切换与终端指令【方法】  Windows11如何设置专注助手_Windows11专注助手使用攻略【技巧】 

 2026-01-04