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

组件设计系列：实现一个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