C++怎么实现一个LRU缓存淘汰算法_C++数据结构设计与LRU Cache实现

尼克

发布时间：2025-12-02 09:43:20

266人浏览过

来源于php中文网

原创

LRU缓存通过哈希表和双向链表组合实现，O(1)完成查找与顺序维护。1. 哈希表映射key到链表节点；2. 链表头部存最近使用项；3. 访问或插入时更新位置；4. 容量超限时删除尾部节点。

c++怎么实现一个lru缓存淘汰算法_c++数据结构设计与lru cache实现

实现一个LRU（Least Recently Used）缓存淘汰算法，核心在于快速访问数据的同时维护访问顺序。当缓存满时，优先淘汰最久未使用的数据。C++中可以通过结合 哈希表（unordered_map） 和 双向链表（list） 高效实现，达到O(1)的查找、插入和删除效率。

基本思路与数据结构选择

为了同时满足快速查找和顺序管理：

unordered_map：存储键（key）到双向链表节点的映射，实现O(1)查找。
list（双向链表）：维护访问顺序，最近使用的放头部，最久未用的在尾部，便于O(1)移动和删除。

每次访问某个key，就将其对应节点移到链表头部；插入新元素时若超出容量，则删除尾部节点。

C++代码实现

以下是一个完整的LRU Cache类实现：

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

百度MCP广场

探索海量可用的MCP Servers

下载

#include 
#include 
#include 

class LRUCache {
private:
    int capacity;
    std::unordered_map>::iterator> cache;
    std::list> used;

public:
    LRUCache(int cap) : capacity(cap) {}

    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) return -1; // 未命中

        // 命中，将该元素移到链表头部
        used.splice(used.begin(), used, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = cache.find(key);
        if (it != cache.end()) {
            // 已存在，更新值并移到头部
            it->second->second = value;
            used.splice(used.begin(), used, it->second);
            return;
        }

        // 新插入，检查是否超容
        if (cache.size() >= capacity) {
            int old_key = used.back().first;
            cache.erase(old_key);
            used.pop_back();
        }

        // 插入新节点到链表头部
        used.emplace_front(key, value);
        cache[key] = used.begin();
    }
};

关键操作说明

splice 是实现高效移动的核心：

used.splice(used.begin(), used, it->second) 将指定节点直接移到链表头部，不涉及内存分配，时间复杂度为O(1)。
避免了先删除再插入带来的开销。

emplace_front 直接在链表头部构造新节点，比 push_front 更高效。

使用示例

int main() {
    LRUCache lru(2);
    lru.put(1, 1);
    lru.put(2, 2);
    std::cout << lru.get(1) << "\n"; // 输出 1
    lru.put(3, 3);                    // 淘汰 key=2
    std::cout << lru.get(2) << "\n"; // 输出 -1
    return 0;
}

基本上就这些。通过哈希表+双向链表的组合，C++能简洁高效地实现LRU缓存，适合面试和实际应用。注意边界处理和STL成员函数的正确使用即可。

c++中如何判断一个数是否为素数_c++判断质数的算法实现【指南】

c++中如何实现简单的HTTP请求_c++使用socket发送GET请求方法【详解】

c++中如何实现简单的观察者模式方案_c++设计模式实战指南【详解】

c++中如何比较浮点数是否相等_c++判断两个double是否相等【汇总】

c++中如何判断字符串是否包含所有元音字母_c++字符搜索逻辑【详解】

相关标签:

c++ ai ios stream red 成员函数数据结构算法

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：c++如何实现解释器设计模式_c++构建简单的语言解释器下一篇：c++如何实现一个享元设计模式_c++ Flyweight模式节约内存

作者最新文章

苹果手机怎么设置默认浏览器_iPhone Safari替换方法

2026-01-19 08:35

Laravel中如何配置环境变量.env_Laravel环境变量读取与生效方法【教程】

2026-01-19 08:49

composer如何将外部库映射到指定命名空间_composer自定义类库加载【实战】

2026-01-19 08:53

todesk和AnyDesk的对比分析_todesk与AnyDesk功能性能对比

2026-01-19 08:55

sublime如何安装Compare Side-By-Side_sublime文件对比插件【详解】

2026-01-19 08:57

CrazyGames官方网站链接 CrazyGames电脑在线免费玩

2026-01-19 09:02

Laravel Eloquent如何实现作用域(Scopes)来复用查询逻辑？ (全局与本地作用域)

2026-01-19 09:05

c++中如何使用std::distance计算迭代器间距离_c++容器技巧【汇总】

2026-01-19 09:18

电脑风扇狂转但CPU温度不高原因揭秘软件设置与清灰建议【实用贴士】

2026-01-19 09:24

失业金怎么领取领取条件及手机APP申请操作流程【指南】

2026-01-19 09:43

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI大模型

开放平台

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI大模型

腾讯元宝

腾讯混元平台推出的AI助手

文档处理

Excel 表格

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI大模型

中文写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

中文写作

写作工具

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接

图画生成

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI大模型

中文写作

智谱清言 - 免费全能的AI助手

AI大模型

PDF 文档

相关专题

treenode的用法

在计算机编程领域，TreeNode是一种常见的数据结构，通常用于构建树形结构。在不同的编程语言中，TreeNode可能有不同的实现方式和用法，通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

535

2023.12.01

C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化，涵盖排序算法（快速排序、归并排序）、查找算法、图算法、动态规划、贪心算法等，并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构（链表、树、堆、哈希表等），帮助开发者提升在复杂应用中的算法设计与性能优化能力。

2025.12.22

深入理解算法：高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念，适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用，如数组、链表、栈、队列、哈希表、树、图等；以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析，帮助开发者不仅能熟练运用这些基础知识，还能在实际编程中优化性能，提高代码的执行效率。本专题适合准备面试的开发者，也适合希望提高算法思维的编程爱好者。

2026.01.06

页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章，大家可以免费体验。

403

2023.08.14

PHP WebSocket 实时通信开发

本专题系统讲解 PHP 在实时通信与长连接场景中的应用实践，涵盖 WebSocket 协议原理、服务端连接管理、消息推送机制、心跳检测、断线重连以及与前端的实时交互实现。通过聊天系统、实时通知等案例，帮助开发者掌握使用 PHP 构建实时通信与推送服务的完整开发流程，适用于即时消息与高互动性应用场景。

2026.01.19

微信聊天记录删除恢复导出教程汇总

本专题整合了微信聊天记录相关教程大全，阅读专题下面的文章了解更多详细内容。

2026.01.18

高德地图升级方法汇总

本专题整合了高德地图升级相关教程，阅读专题下面的文章了解更多详细内容。

108

2026.01.16

全民K歌得高分教程大全

本专题整合了全民K歌得高分技巧汇总，阅读专题下面的文章了解更多详细内容。

152

2026.01.16

C++ 单元测试与代码质量保障

本专题系统讲解 C++ 在单元测试与代码质量保障方面的实战方法，包括测试驱动开发理念、Google Test/Google Mock 的使用、测试用例设计、边界条件验证、持续集成中的自动化测试流程，以及常见代码质量问题的发现与修复。通过工程化示例，帮助开发者建立可测试、可维护、高质量的 C++ 项目体系。

2026.01.16

热门下载

网站特效

网站源码

网站素材

前端模板