LRU缓存的全称是最近最少使用缓存，当缓存容量达到上限时，会优先移除最久没有被访问的数据。在C++中实现LRU缓存，通常会结合map和list两种容器，利用它们各自的特性简化实现逻辑。
LRU缓存的核心规则
LRU缓存需要支持两个核心操作：
- 获取数据：如果key存在，返回对应的值，同时将该数据标记为最近使用；如果不存在，返回特定标识。
- 写入数据：如果key不存在，插入新数据，若缓存已满则先淘汰最久未使用的数据；如果key已存在，更新对应的值，同时将该数据标记为最近使用。
map和list的作用分工
在C++的实现中，两种容器的分工非常明确：
list：用来维护数据的访问顺序，list的头部存放最近使用的数据，尾部存放最久未使用的数据。list中的元素是键值对，方便后续淘汰时直接获取对应的key。map：用来存储key到list迭代器的映射，这样可以在O(1)时间复杂度内找到某个key在list中的位置，避免遍历list带来的性能损耗。
完整实现代码
以下是基于C++标准库实现的LRU缓存完整代码：
#include <iostream>
#include <unordered_map>
#include <list>
#include <utility>
using namespace std;
class LRUCache {
private:
int capacity; // 缓存容量
// list存储键值对，头部是最近使用，尾部是最久未使用
list<pair<int, int>> cacheList;
// map存储key到list迭代器的映射
unordered_map<int, list<pair<int, int>>::iterator> cacheMap;
public:
// 构造函数，初始化缓存容量
LRUCache(int cap) : capacity(cap) {}
// 获取缓存数据
int get(int key) {
// 如果key不存在，返回-1
if (cacheMap.find(key) == cacheMap.end()) {
return -1;
}
// key存在，将对应节点移动到list头部，标记为最近使用
auto iter = cacheMap[key];
cacheList.splice(cacheList.begin(), cacheList, iter);
return iter->second;
}
// 写入缓存数据
void put(int key, int value) {
// 如果key已经存在，更新值并移动到头部
if (cacheMap.find(key) != cacheMap.end()) {
auto iter = cacheMap[key];
iter->second = value;
cacheList.splice(cacheList.begin(), cacheList, iter);
return;
}
// 如果缓存已满，淘汰尾部的最久未使用数据
if (cacheList.size() == capacity) {
auto lastNode = cacheList.back();
int lastKey = lastNode.first;
cacheMap.erase(lastKey);
cacheList.pop_back();
}
// 插入新数据到list头部，并更新map
cacheList.push_front({key, value});
cacheMap[key] = cacheList.begin();
}
};
// 测试代码
int main() {
LRUCache cache(2);
cache.put(1, 1);
cache.put(2, 2);
cout << cache.get(1) << endl; // 返回1
cache.put(3, 3); // 该操作会让key=2被淘汰
cout << cache.get(2) << endl; // 返回-1
cache.put(4, 4); // 该操作会让key=1被淘汰
cout << cache.get(1) << endl; // 返回-1
cout << cache.get(3) << endl; // 返回3
cout << cache.get(4) << endl; // 返回4
return 0;
}
代码逻辑解析
get操作解析
首先通过map查找key是否存在，若不存在直接返回-1。若存在，获取到对应的list迭代器，使用list的splice方法将该节点移动到list头部，时间复杂度为O(1)，最后返回对应的值。
put操作解析
如果key已存在，更新对应的值，再将节点移动到list头部。如果key不存在，先判断缓存是否已满，满了则先通过list的back方法获取尾部节点，取出key从map中删除，再从list中弹出尾部节点。最后将新节点插入list头部，同时在map中记录key到迭代器的映射。
复杂度分析
两种核心操作的时间复杂度都是O(1)，因为map的查找、插入、删除都是O(1)平均复杂度，list的头部插入、删除、节点移动也是O(1)复杂度。空间复杂度为O(capacity)，即缓存容量大小。