欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

组件设计系列:实现一个LRU缓存类

程序员文章站 2022-06-25 21:44:56
组件设计系列:实现一个LRU缓存类1、简介2、实现LRU缓存3、测试1、简介在我负责的项目中,有很多公共的组件,实现的思路很值得我们学习。比如LRU缓存,这种策略在操作系统中也有应用。本次是基于C++实现的一个支持泛型的LRU缓存工具类,实现思路供大家参考。LRU算法(Least Recently Used,最近最少使用),是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。2、实现LRU缓存首先看一下LRUCache类的定义如下:思路主要是借助map和list来实现一个LRU缓存的实...

组件设计系列:实现一个LRU缓存类

1、简介

在我负责的项目中,有很多公共的组件,实现的思路很值得我们学习。比如LRU缓存,这种策略在操作系统中也有应用。本次是基于C++实现的一个支持泛型的LRU缓存工具类,实现思路供大家参考。
LRU算法(Least Recently Used,最近最少使用),是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。

2、实现LRU缓存

首先看一下LRUCache类的定义如下:
组件设计系列:实现一个LRU缓存类
思路主要是借助map和list来实现一个LRU缓存的实现,其中map用于快速查找,list用于顺序存储。map的key为数据的key,Value为list的元素指针。List中也存放具体的元素key-Value值。其中分别实现的函数主要包括有参构造函数,析构函数,put和get方法,以及返回整个LRU缓存的数据get_list方法。

先看看构造函数和析构函数的实现,其中构造函数为有参数构造。参数cap代表了LRU缓存的容量。当存放的数据多于cap,则会剔除最老的数据。
组件设计系列:实现一个LRU缓存类
接下来看看存放数据的put方法,实现源码如下。
组件设计系列:实现一个LRU缓存类
put方法存放数据的时候,首先查找一下是否存在该Key,如果存在则先删除该元素,然后再重新加入list中头部,这样当前元素就是最热的数据了。如果不存在该key-Value,首先存放新的key-Value到list头部,然后需要看看LRU中是否满了,如果满了则需要释放list最后一个数据。比如存放第一个数据,键值对为《 2,“DOG”》时候,当再次放入一个新的数据,《3,“CAT”》的时候,LRU缓存是这样的。
组件设计系列:实现一个LRU缓存类
我们来看看get方法是如何获取元素的,源码如下。
组件设计系列:实现一个LRU缓存类
get方法的思路比较简单,就是先在map中查找是否存在当前Key,如果不存在,则直接返回。如果存在,则需要更新当前数据的热度,也就是需要将当前元素移动到list头部位置。这里还是先从list中删除该Key-Value,然后再存放到list头部即可。

3、测试

最后来看一下测试案例,测试案例比较简单。
组件设计系列:实现一个LRU缓存类
总的来说,LRU还是比较容易实现的,在面试中也会遇到,虽然比较简单,但是也需要提高动手能力,保证面试的时候能够一次性写出来,不出错。

喜欢本文的朋友,也可以关注本人微信公众号“码农的修炼之道”,更多精彩文章等你来阅读!

本文地址:https://blog.csdn.net/wengsuwei7683/article/details/109628210