C++实现LRU缓存（新手入门详解）

在这里插入图片描述

LRU的概念

LRU（Least Recently Used，最近最少使用）是一种常用的缓存淘汰策略，主要目的是在缓存空间有限的情况下，优先淘汰那些最长时间没有被访问的数据项。LRU 策略的核心思想是：

  1. 缓存空间有限：缓存只能存储一定数量的数据项。

  2. 淘汰最不常用的数据：当缓存满时，优先淘汰那些最近最少被访问的数据项。

  3. 访问记录：每次数据项被访问时，都会更新其访问记录，使得最近访问的数据项保留在缓存中。

  4. 数据替换：当需要加载新数据项到缓存中，但缓存已满时，会根据LRU策略淘汰一个或多个数据项，为新数据项腾出空间。

  5. 动态调整：随着数据访问模式的变化，LRU策略可以动态调整缓存中的数据项，以适应访问模式的变化。

在实现LRU缓存时，通常会使用数据结构如哈希表和双向链表。哈希表用于快速定位缓存中的数据项，而双向链表则用于维护数据项的访问顺序。每次访问数据项时，都会将其移动到链表的头部，表示它是最近被访问的。当需要淘汰数据时，直接从链表的尾部开始淘汰即可。

LRU策略在许多场景中都非常有用，比如操作系统的页面置换、数据库的查询缓存、Web服务器的页面缓存等。它可以帮助系统更有效地利用有限的缓存资源，提高系统的整体性能。
在这里插入图片描述在这里插入图片描述
别急，我们先学实现LRU要用的哈希表和双向链表

哈希表（unordered_map）

在C++中，unordered_map 是标准模板库（STL）中的一个关联容器，它基于哈希表的实现。它存储了键值对，允许通过键快速访问和修改值。unordered_map 提供了平均常数时间复杂度的访问、插入和删除操作。

主要特性

  1. 基于哈希表：通过哈希函数将键映射到存储位置，实现快速查找。
  2. 键不重复：每个键在容器中是唯一的。
  3. 无序存储：元素的存储顺序不依赖于插入顺序，因此迭代器的遍历顺序可能与插入顺序不同。

常用操作

  • 构造和初始化：

    • unordered_map()：创建一个空的 unordered_map。
    • unordered_map(initializer_list<value_type>)：使用初始化列表创建 unordered_map。

  • 插入操作：

    • insert(value_type)：插入一个键值对。
    • insert(initializer_list<value_type>)：插入多个键值对。

  • 访问操作：

    • operator[]：通过键访问对应的值，如果键不存在，则插入一个新元素。
    • at(key)：通过键访问对应的值，如果键不存在，则抛出 std::out_of_range 异常。

  • 查找操作：

    • find(key)：查找键是否存在，返回一个迭代器。
    • count(key)：返回键出现的次数（对于 unordered_map 总是返回 0 或 1）。

  • 删除操作：

    • erase(it)：删除迭代器 it 指向的元素。
    • erase(first, last)：删除从 first 到 last（不包括 last）范围内的所有元素。
    • erase(key)：删除指定键的所有元素。

  • 大小和容量：

    • size()：返回容器中元素的数量。
    • empty()：如果容器为空，返回 true。

  • 迭代器：

    • begin()：返回指向容器开始的迭代器。
    • end()：返回指向容器结束的迭代器。

示例代码

以下是使用 unordered_map 的一个简单示例：

#include <iostream>
#include <unordered_map>int main() {// 创建一个 unordered_map，键为 int，值为 stringunordered_map<int, string> umap;// 插入元素umap[1] = "one";umap[2] = "two";umap[3] = "three";// 访问并打印元素for (const auto& pair : umap) {std::cout << pair.first << ": " << pair.second << std::endl;}// 访问特定键的值try {std::cout << "Value for key 2: " << umap.at(2) << std::endl;} catch (const std::out_of_range& e) {std::cerr << e.what() << std::endl;}// 查找键是否存在auto it = umap.find(3);if (it != umap.end()) {std::cout << "Key 3 found, value: " << it->second << std::endl;}// 删除元素umap.erase(2);std::cout << "After erasing key 2:" << std::endl;for (const auto& pair : umap) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}

输出：

1: one
2: two
3: three
Value for key 2: two
Key 3 found, value: three
After erasing key 2:
1: one
3: three

在这个示例中：

  • 创建了一个 unordered_map 并插入了一些键值对。
  • 遍历并打印了 unordered_map 中的所有元素。
  • 使用 at() 方法安全地访问特定键的值。
  • 使用 find() 方法查找键是否存在，并访问对应的值。
  • 使用 erase() 方法删除了键为 2 的元素，并再次打印了剩余的元素。

双向链表（list）

在C++中，list 是标准模板库（STL）中的一个容器类，它提供了双向链表的实现。与数组或向量（vector）不同，list 允许在任意位置高效地插入和删除元素，而不需要移动其他元素。

以下是 list 的一些主要特性和常用操作：

特性

  1. 双向链表：每个元素都是链表中的一个节点，可以从前向后或从后向前遍历。
  2. 动态大小：list 的大小可以根据需要动态变化，不需要预先定义大小。
  3. 插入和删除操作：可以在常数时间内在任意位置插入或删除元素，不需要像 vector 那样移动其他元素。

常用操作

  • 插入操作：

    • push_front(value)：在链表头部插入一个元素。
    • push_back(value)：在链表尾部插入一个元素。
    • insert(position, value)：在指定位置插入一个元素。
    • insert(position, n, value)：在指定位置插入 n 个相同的元素。
    • insert(position, first, last)：在指定位置插入一个范围内的元素。

  • 删除操作：

    • pop_front()：删除链表头部的元素。
    • pop_back()：删除链表尾部的元素。
    • erase(position)：删除指定位置的元素。
    • erase(first, last)：删除从 first 到 last（不包括 last）范围内的所有元素。

  • 访问操作：

    • front()：返回链表头部的元素。
    • back()：返回链表尾部的元素。

  • 迭代器：

    • begin()：返回指向链表头部的迭代器。
    • end()：返回指向链表尾部的迭代器。

  • 大小和容量：

    • size()：返回链表中元素的数量。
    • empty()：如果链表为空，返回 true。

示例代码

以下是使用 list 的一个简单示例：

#include <iostream>
#include <list>int main() {list<int> myList;// 向链表中添加元素myList.push_back(10);myList.push_back(20);myList.push_front(5);// 访问并打印链表中的元素for (list<int>::iterator it = myList.begin(); it != myList.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 删除头部元素myList.pop_front();std::cout << "After popping front: ";for (auto it = myList.begin(); it != myList.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 删除尾部元素myList.pop_back();std::cout << "After popping back: ";for (auto it = myList.begin(); it != myList.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}

输出：

5 10 20 
After popping front: 10 20 
After popping back: 10

在这个示例中，我们创建了一个 list 并添加了一些整数元素。然后，我们遍历并打印链表中的元素，删除头部和尾部的元素，并再次打印链表中的元素。

在这里插入图片描述
到这里，你已经掌握实现LRU缓存的两个条件了，马上你就要成功了！！！

真的，不信你往下看！

LRU缓存（C++）

#include <iostream>
#include <list>
#include <unordered_map>// 使用 using namespace std; 来简化代码，避免重复书写 std:: 前缀
using namespace std;// LRUCache 类定义
class LRUCache {
private:int capacity;  // 缓存的容量list<int> keys;  // 使用双向链表存储键，保持访问顺序unordered_map<int, pair<int, list<int>::iterator>> cache;  // 存储键值对和对应的链表迭代器public:// 构造函数，初始化缓存容量LRUCache(int capacity) : capacity(capacity) {}// 获取缓存中键对应的值int get(int key) {auto it = cache.find(key);if (it == cache.end()) {return -1;  // 如果键不存在，返回 -1}// 更新访问顺序，将该键移动到链表头部keys.erase(it->second.second);keys.push_front(key);it->second.second = keys.begin();return it->second.first;  // 返回键对应的值}// 插入或更新缓存中的键值对void put(int key, int value) {if (cache.size() >= capacity && cache.find(key) == cache.end()) {// 如果缓存已满且键不存在，淘汰最不常用的键（链表尾部的键）auto last = keys.back();cache.erase(cache.find(last));keys.pop_back();}// 插入或更新键值对，并更新访问顺序cache[key] = {value, keys.insert(keys.begin(), key)};}
};int main() {// 创建一个容量为 2 的 LRU 缓存LRUCache cache(2);// 插入键值对 (1, 1)cache.put(1, 1);// 访问键 1，输出其值cout << "get(1) = " << cache.get(1) << endl; // 返回 1// 插入键值对 (2, 2)cache.put(2, 2);// 访问键 2，输出其值cout << "get(2) = " << cache.get(2) << endl; // 返回 2// 插入键值对 (3, 3)，由于缓存已满，键 1 被淘汰cache.put(3, 3);// 访问键 1，由于已被淘汰，返回 -1cout << "get(1) = " << cache.get(1) << endl; // 返回 -1// 访问键 3，输出其值cout << "get(3) = " << cache.get(3) << endl; // 返回 3// 插入键值对 (4, 4)，由于缓存已满，键 2 被淘汰cache.put(4, 4);// 访问键 1，由于已被淘汰，返回 -1cout << "get(1) = " << cache.get(1) << endl; // 返回 -1// 访问键 3，输出其值cout << "get(3) = " << cache.get(3) << endl; // 返回 3// 访问键 2，由于已被淘汰，返回 -1cout << "get(2) = " << cache.get(2) << endl; // 返回 -1// 访问键 4，输出其值cout << "get(4) = " << cache.get(4) << endl; // 返回 4return 0;
}

这段代码首先定义了一个 LRUCache 类，该类使用 unordered_map 和 list 来实现 LRU 缓存机制。get 方法用于获取缓存中的值，如果键存在，则返回其值并更新访问顺序；如果键不存在，则返回 -1。put 方法用于插入或更新缓存中的键值对，如果缓存已满，则淘汰最不常用的键（链表尾部的键）。在 main 函数中，创建了一个 LRUCache 对象并进行了一些操作来演示其功能。

在这里插入图片描述

什么？看不懂？没关系，结合下面的过程看，你应该就明白了！

初始化状态

Cache: {}
Keys: []

执行 cache.put(1, 1)

Cache: {1: (1, it1)}
Keys: [1]

执行 cache.put(2, 2)

Cache: {1: (1, it1), 2: (2, it2)}
Keys: [2, 1]  (2 最近使用，1 最少使用)

执行 cache.put(3, 3)

  • 缓存已满，淘汰键 1
Cache: {2: (2, it2), 3: (3, it3)}
Keys: [3, 2]  (3 最近使用，2 次之)

执行 cache.get(1)

  • 键 1 不存在，返回 -1
Cache: {2: (2, it2), 3: (3, it3)}
Keys: [3, 2]

执行 cache.get(3)

  • 键 3 存在，返回 3，并更新为最近使用
Cache: {2: (2, it2), 3: (3, it3)}
Keys: [3, 2]

执行 cache.put(4, 4)

  • 缓存已满，淘汰键 2
Cache: {3: (3, it3), 4: (4, it4)}
Keys: [4, 3]  (4 最近使用，3 次之)

执行 cache.get(1)

  • 键 1 不存在，返回 -1
Cache: {3: (3, it3), 4: (4, it4)}
Keys: [4, 3]

执行 cache.get(3)

  • 键 3 存在，返回 3，并更新为最近使用
Cache: {3: (3, it3), 4: (4, it4)}
Keys: [3, 4]

执行 cache.get(2)

  • 键 2 不存在，返回 -1
Cache: {3: (3, it3), 4: (4, it4)}
Keys: [3, 4]

执行 cache.get(4)

  • 键 4 存在，返回 4，并更新为最近使用
Cache: {3: (3, it3), 4: (4, it4)}
Keys: [4, 3]

在这里插入图片描述
至此，你就算没有台明白，也一定了解LRU了。收藏可以方便下次巩固哦！！！！
在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/1486060.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

深入浅出C语言指针(进阶篇)

深入浅出C语言指针(进阶篇)

深入浅出C语言指针(基础篇) 深入浅出C语言指针(进阶篇) 目录 引言 一、指针和数组 1.数组名的理解 2.指针访问数组 3.一维数组传参的本质 二、二级指针 1.二级指针的概念 2.二级指针的内存表示 3.二级指针的解引用 三、字符指针 1.指针指向单个字符 2.指针指向字…
阅读更多...
【目标检测】Anaconda+PyTorch配置

【目标检测】Anaconda+PyTorch配置

前言 本文主要介绍在windows系统上的Anaconda、PyTorch关键步骤安装&#xff0c;为使用yolo所需的环境配置完善。同时也算是记录下我的配置流程&#xff0c;为以后用到的时候能笔记查阅。 Anaconda 软件安装 Anaconda官网&#xff1a;https://www.anaconda.com/ 另外&#…
阅读更多...
Golang | Leetcode Golang题解之第278题第一个错误的版本

Golang | Leetcode Golang题解之第278题第一个错误的版本

题目&#xff1a; 题解&#xff1a; func firstBadVersion(n int) int {return sort.Search(n, func(version int) bool { return isBadVersion(version) }) }
阅读更多...
Elasticsearch基础（六）：使用Kibana Lens进行数据可视化

Elasticsearch基础（六）：使用Kibana Lens进行数据可视化

文章目录 使用Kibana Lens进行数据可视化 一、进入Kibana Lens 二、基础可视化 1、指标可视化 2、垂直堆积条形图 3、表格 三、高级可视化 1、多图层和索引 2、子桶 3、树状图 使用Kibana Lens进行数据可视化 一、进入Kibana Lens 在Kibana主页&#xff0c;单击页面…
阅读更多...
vxe-table——实现切换页码时排序状态的回显问题（ant-design+elementUi中table排序不同时回显的bug）——js技能提升

vxe-table——实现切换页码时排序状态的回显问题（ant-design+elementUi中table排序不同时回显的bug）——js技能提升

之前写的后台管理系统&#xff0c;都是用的antdelement&#xff0c;table组件中的【排序】问题是有一定的缺陷的。 想要实现的效果&#xff1a; antv——table组件一次只支持一个参数的排序 如下图&#xff1a; 就算是可以自行将排序字段拼接到列表接口的入参中&#xff0c…
阅读更多...
Druid【基础 01】是什么+主要特点+设计原则+架构+数据结构（简单入门Druid）

Druid【基础 01】是什么+主要特点+设计原则+架构+数据结构（简单入门Druid）

Druid入门 1. 是什么2. 主要特点3. 三个设计原则4. Architecture 架构5. 数据结构5.1 DataSource 结构5.2 Segment 结构 Druid 非中文官网&#xff0c;内容不少且介绍的挺详细的&#xff0c;需要英文阅读能力或者翻译工具进行辅助。 1. 是什么 先看看官网怎么说&#xff1a; A…
阅读更多...
请你谈谈：spring bean的生命周期 - 阶段5：BeanPostProcessor前置处理-自定义初始化逻辑-BeanPostProcess后置处理

请你谈谈：spring bean的生命周期 - 阶段5：BeanPostProcessor前置处理-自定义初始化逻辑-BeanPostProcess后置处理

BeanPostProcessor的postProcessBeforeInitialization方法是在bean的依赖注入&#xff08;即属性填充&#xff09;完成后&#xff0c;但在bean的初始化回调&#xff08;如PostConstruct注解的方法或InitializingBean接口的afterPropertiesSet方法&#xff09;之前被调用的。 具…
阅读更多...
证书上的服务器名错误解决方法

证书上的服务器名错误解决方法

方法 win r &#xff0c;输入mmc 点击文件——>添加/删除管理单元 找到证书——> 添加 根据自己的存放选择存放位置 点击控制台根节点——> 受信任的根证书颁发机构——>导入 若还出现问题&#xff0c;则参考https://blog.csdn.net/mm120138687/article/details/…
阅读更多...
立创梁山派--移植开源的SFUD万能的串行 Flash 通用驱动库

立创梁山派--移植开源的SFUD万能的串行 Flash 通用驱动库

SFUD是什么 关于SFUD库的介绍&#xff0c;其开源链接(gitee,github)已经详细的阐述了. 这里是截取自它的一部分介绍&#xff1a; SFUD 是一款开源的串行 SPI Flash 通用驱动库。由于现有市面的串行 Flash 种类居多&#xff0c;各个 Flash 的规格及命令存在差异&#xff0c; SF…
阅读更多...
Apache Tomcat文件包含漏洞复现(详细教程)

Apache Tomcat文件包含漏洞复现(详细教程)

1.漏洞原理 Tomcat 服务器是一个免费的开放源代码的Web 应用服务器&#xff0c;其安装后会默认开启ajp连接器&#xff0c;方便与其他web服务器通过ajp协议进行交互。属于轻量级应用服务器&#xff0c;在中小型系统和并发访问用户不是很多的场合下被普遍使用&#xff0c;是开发和…
阅读更多...
【接口自动化_07课_Pytest+Excel+Allure完整框架集成_下】

【接口自动化_07课_Pytest+Excel+Allure完整框架集成_下】

目标&#xff1a;优化框架场景 1. 生成对应的接口关联【重点】 2. 优化URL基础路径封装【理解】 3. 利用PySQL操作数据库应用【理解】--- 怎么用python连接数据库、mysql 4. 通过数据库进行数据库断言【重点】 5. 通过数据库进行关联操作【重点】 一、接口关联&#xff1a…
阅读更多...
MSP430M03507最小系统板的keil环境搭配，用keil编辑ti单片机

MSP430M03507最小系统板的keil环境搭配，用keil编辑ti单片机

转载自嘉立创MSP430M03507开发手册 这篇文章只是因为我的keil版本与嘉立创的不一样&#xff0c;所以添加了我自己遇到的问题解析 先说说为什么要用keil编辑&#xff0c;因为ti单片机自己的ccs编译环境需要对应仿真器&#xff0c;那个加芯片都240了&#xff0c;哪有那么多钱买…
阅读更多...
node.js中nodemon : 无法加载和使用问题，这是由于windows安全策略影起的按如下操作即可

node.js中nodemon : 无法加载和使用问题，这是由于windows安全策略影起的按如下操作即可

1、用管理员权限打开vscode 2、文件终端中打开&#xff0c;输入 Set-ExecutionPolicy -Scope CurrentUser 3、再输入RemoteSigned 4、使用get-ExecutionPolicy查看权限&#xff0c;可以看到变为了RemoteSigned 重启问题解决
阅读更多...
MySQL面试索引篇

MySQL面试索引篇

1、什么是索引&#xff1f; 作为一个数据库&#xff0c;首要任务就是把数据存储好&#xff0c;并快速查询出用户需要的数据&#xff0c;而索引就相当于图书的目录一样&#xff0c;是一种用于快速查询和检索数据的数据结构&#xff0c;其本质可以看成是一种排序好的数据结构。 …
阅读更多...
TypeScript 教程(九)：类型声明文件与异步编程

TypeScript 教程(九)：类型声明文件与异步编程

目录 前言回顾装饰器与高级类型操控1. 类型声明文件a. 什么是类型声明文件&#xff08;.d.ts&#xff09;b. 编写和使用类型声明文件 2. 异步编程a. Promise 类型b. async/awaitc. 异步迭代器 3. 并行执行与错误处理a. Promise.allb. Promise.racec. 错误处理 结语 前言 在前几…
阅读更多...
华为云.云日志服务LTS及其基本使用

华为云.云日志服务LTS及其基本使用

云计算 云日志服务LTS及其基本使用 - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this article:https://blog.csdn.net/qq_28550…
阅读更多...
数学建模（7）——Logistic模型

数学建模（7）——Logistic模型

一、马尔萨斯人口模型 import numpy as np import matplotlib.pyplot as plt# 初始人口 N0 100 # 人口增长率 r 0.02 # 时间段&#xff08;年&#xff09; t np.linspace(0, 200, 200)# 马尔萨斯人口模型 N N0 * np.exp(r * t)# 绘图 plt.plot(t, N, labelPopulation) plt.…
阅读更多...
图片转pdf的软件有哪些？这几种转换工具了解下

图片转pdf的软件有哪些？这几种转换工具了解下

在日常的办公学习中&#xff0c;图片转PDF的需求愈发普遍。不论是工作汇报、学习笔记还是生活点滴&#xff0c;我们都希望将重要的图片内容整理成易于查阅的PDF格式。那么&#xff0c;有哪些软件可以做到将图片转换成PDF格式呢&#xff1f;给大家介绍5种简单好用的转换方法&…
阅读更多...
Linux第五节课（权限02）

Linux第五节课（权限02）

1、Linux下的用户分类 root&#xff1a;超级用户普通用户&#xff1a;通过root新建的用户&#xff0c;adduser root不受权限约束&#xff1b;普通用户受权限约束&#xff1b; Linux系统中&#xff0c;所有用户都需要有密码&#xff0c;无论是root还是其他&#xff0c;即便是…
阅读更多...
SpringBoot+ Sharding Sphere 轻松实现数据库字段加解密

SpringBoot+ Sharding Sphere 轻松实现数据库字段加解密

一、介绍 在实际的软件系统开发过程中&#xff0c;由于业务的需求&#xff0c;在代码层面实现数据的脱敏还是远远不够的&#xff0c;往往还需要在数据库层面针对某些关键性的敏感信息&#xff0c;例如&#xff1a;身份证号、银行卡号、手机号、工资等信息进行加密存储&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023