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++免费学习笔记（深入）”；

美图AI开放平台

美图推出的AI人脸图像处理平台

下载

#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++中如何使用std::regex_search_c++正则表达式搜索匹配项【实例】

c++ ifdef ifndef用法_c++条件编译指令详解

c++中如何判断字符串是否符合Email格式_c++正则表达式应用【详解】

c++中如何实现字符串的快速匹配算法_c++ Sunday算法实现步骤【详解】

c++中如何计算次幂_c++ pow函数的使用方法【详解】

相关标签:

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

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

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

作者最新文章

米哈游通行证怎么查看实名认证身份信息查询方法【详解】

2026-01-22 08:37

电脑开机自检很久怎么办_关闭电脑开机磁盘检查方法【教程】

2026-01-22 08:38

好分数查分登录入口好分数网页版登录页面

2026-01-22 08:39

1纳米是多少米 1纳米有多小

2026-01-22 08:42

苹果手机怎么查看电池健康度_苹果手机电池寿命查询与保养指南【必看】

2026-01-22 08:57

久久小说网永久官网地址久久小说网免费小说门户

2026-01-22 09:16

composer如何配置项目默认安装路径_composer更改vendor目录名称方法【教程】

2026-01-22 09:25

电脑启动提示No Bootable Device？排查电脑硬盘引导故障【教程】

2026-01-22 09:29

冬天穿高领毛衣脖子痒怎么办材质选择建议【实用】

2026-01-22 09:33

如何使用Unity C++ Scripting替代C#？ (DOTS技术栈)

2026-01-22 09:34

热门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中文网欢迎大家前来学习。

536

2023.12.01

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

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

2025.12.22

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

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

2026.01.06