组件设计系列:实现一个LRU缓存类
1、简介
在我负责的项目中,有很多公共的组件,实现的思路很值得我们学习。比如LRU缓存,这种策略在操作系统中也有应用。本次是基于C++实现的一个支持泛型的LRU缓存工具类,实现思路供大家参考。
LRU算法(Least Recently Used,最近最少使用),是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。
2、实现LRU缓存
首先看一下LRUCache类的定义如下:
思路主要是借助map和list来实现一个LRU缓存的实现,其中map用于快速查找,list用于顺序存储。map的key为数据的key,Value为list的元素指针。List中也存放具体的元素key-Value值。其中分别实现的函数主要包括有参构造函数,析构函数,put和get方法,以及返回整个LRU缓存的数据get_list方法。
先看看构造函数和析构函数的实现,其中构造函数为有参数构造。参数cap代表了LRU缓存的容量。当存放的数据多于cap,则会剔除最老的数据。
接下来看看存放数据的put方法,实现源码如下。
put方法存放数据的时候,首先查找一下是否存在该Key,如果存在则先删除该元素,然后再重新加入list中头部,这样当前元素就是最热的数据了。如果不存在该key-Value,首先存放新的key-Value到list头部,然后需要看看LRU中是否满了,如果满了则需要释放list最后一个数据。比如存放第一个数据,键值对为《 2,“DOG”》时候,当再次放入一个新的数据,《3,“CAT”》的时候,LRU缓存是这样的。
我们来看看get方法是如何获取元素的,源码如下。
get方法的思路比较简单,就是先在map中查找是否存在当前Key,如果不存在,则直接返回。如果存在,则需要更新当前数据的热度,也就是需要将当前元素移动到list头部位置。这里还是先从list中删除该Key-Value,然后再存放到list头部即可。
3、测试
最后来看一下测试案例,测试案例比较简单。
总的来说,LRU还是比较容易实现的,在面试中也会遇到,虽然比较简单,但是也需要提高动手能力,保证面试的时候能够一次性写出来,不出错。
喜欢本文的朋友,也可以关注本人微信公众号“码农的修炼之道”,更多精彩文章等你来阅读!
本文地址:https://blog.csdn.net/wengsuwei7683/article/details/109628210