c++怎么实现一个LRU缓存算法_c++中LRU缓存的设计与实现

裘德小鎮的故事

发布时间：2025-11-11 02:05:35

964人浏览过

来源于php中文网

原创

LRU缓存通过哈希表和双向链表结合实现，get和put操作均O(1)：哈希表映射key到链表节点，链表维护访问顺序，最近使用置头，满时删尾。

c++怎么实现一个lru缓存算法_c++中lru缓存的设计与实现

实现一个LRU（Least Recently Used）缓存的核心思路是：当缓存满时，优先淘汰最久未使用的数据。为了高效地完成插入、查找和更新操作，C++中通常结合哈希表（unordered_map）和双向链表（list）来实现。

1. LRU缓存的基本要求

一个LRU缓存需要支持以下两个核心操作：

get(key)：如果键存在，返回对应的值，并将该键移到最近使用位置；否则返回 -1。
put(key, value)：插入或更新键值对。如果超出容量，删除最久未使用的条目。

这两个操作的时间复杂度都应为 O(1)。

2. 数据结构选择

要达到 O(1) 的时间复杂度，可以这样设计：

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

知了追踪

AI智能信息助手，智能追踪你的兴趣资讯

下载

unordered_mapair>::iterator>：用于快速定位某个 key 是否存在及其在链表中的位置。
list>：双向链表存储键值对，最近使用的放在链表头部，最久未使用的在尾部。

这种组合既能快速查找，又能高效地移动和删除节点。

3. 实现代码示例

#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;
        }

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

        // 如果超过容量，删除尾部元素
        if (cache.size() > capacity) {
            int lastKey = used.back().first;
            cache.erase(lastKey);
            used.pop_back();
        }
    }
};

4. 关键点说明

splice 是关键操作：它可以把链表中的某个迭代器指向的节点“剪切”并粘贴到另一个位置，不会导致迭代器失效，且时间复杂度为 O(1)。

每次 get 或 put 已存在的 key 时，都要调用 splice 将其移到链表头部。
新插入的元素直接加到头部，淘汰时从尾部移除。
哈希表保存的是 list 的 iterator，可以直接访问对应节点。

基本上就这些。这个实现简洁、高效，适合面试和实际项目中使用。注意边界情况处理，比如容量为 0 或重复插入等情况即可。不复杂但容易忽略细节。

如何用C++实现一个ECS（实体组件系统）？C++游戏引擎架构模式【游戏开发】

C++如何实现一个简单的A*寻路算法_C++游戏AI开发中的路径规划实战

C++如何实现一个简单的行为树_C++游戏AI中决策逻辑的行为树实现

c++ 矩阵乘法代码 c++矩阵运算实现教程

c++怎么使用ONNX Runtime来运行一个AI模型_C++与ONNX Runtime集成运行AI模型实践

c++速学教程(入门到精通)

c++怎么学习？c++怎么入门？c++在哪学？c++怎么学才快？不用担心，这里为大家提供了c++速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！

下载

相关标签:

ai c++ ios stream 键值对 red int 数据结构算法

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

上一篇：C++怎么实现KMP算法_C++字符串匹配算法与KMP实现下一篇：c++中cout和cin是什么_C++标准输入输出流用法

作者最新文章

MacBook电池健康度怎么看_延长Mac电池寿命的技巧【分享】

2025-12-30 16:08

手机怎么抓拍【技巧】

2025-12-30 16:09

火狐浏览器插件怎么安装_Firefox附加组件安装和管理教程【扩展】

2025-12-30 16:19

siri有什么好玩的用法功能【推荐】

2025-12-30 16:21

c++如何实现并查集算法_c++ 路径压缩与按秩合并优化【案例】

2025-12-30 16:23

Win11怎么创建桌面快捷方式_Windows 11网页与程序快捷方式制作【详解】

2025-12-30 16:27

电脑摄像头怎么打开电脑前置摄像头的打开方式【教程】

2025-12-30 16:27

composer怎么配置自动化代码风格检查_composer引入php-cs-fixer【教程】

2025-12-30 16:28

Mac的iCloud云盘如何使用？（文件同步与管理）

2025-12-30 16:30

如何通过Composer安装PHP-CS-Fixer并配置脚本_使用Composer统一团队代码风格

2025-12-30 16:38

热门AI工具

DeepSeek

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

AI大模型

开放平台

豆包大模型

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

AI大模型

通义千问

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

AI大模型

腾讯元宝

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

文档处理

Excel 表格

文心一言

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

AI大模型

中文写作

讯飞写作

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

中文写作

写作工具

即梦AI

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

图片拼接

图画生成

ChatGPT

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

AI大模型

中文写作

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

AI大模型

PDF 文档

相关专题

string转int

在编程中，我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算，或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章，欢迎大家前来学习阅读。

312

2023.08.02

int占多少字节

int占4个字节，意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值，在某些情况下也可能是2个字节或8个字节，int是一种常用的数据类型，用于表示整数，需要根据具体情况选择合适的数据类型，以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容，供大家免费下载体验。

521

2024.08.29