LRU缓存的全称是最近最少使用缓存，当缓存空间不足时，会优先移除最久没有被访问的数据。在C++中实现LRU缓存，需要兼顾查询效率和数据淘汰的效率，通常选择哈希表配合双向链表的结构来完成。
LRU缓存的核心需求
一个完整的LRU缓存需要支持两个核心操作：
- 获取数据：如果key存在于缓存中，返回对应的value，同时将该数据标记为最近使用；如果不存在，返回特定标识。
- 写入数据：如果key已经存在，更新对应的value，并将该数据标记为最近使用；如果不存在，插入新的键值对。如果缓存容量已满，需要先删除最久未使用的数据，再插入新数据。
数据结构选型分析
为什么选择哈希表加双向链表？
- 哈希表可以实现O(1)时间复杂度的key查询，快速定位到缓存中的数据节点。
- 双向链表可以维护数据的访问顺序，最近访问的节点放在链表头部，最久未访问的节点在链表尾部，删除尾部节点和移动节点到头部都可以在O(1)时间内完成。
节点结构设计
双向链表的节点需要存储key、value，以及前驱和后继指针，方便链表的插入和删除操作：
struct Node {
int key;
int value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
LRU缓存完整实现
我们封装一个LRUCache类，内部维护哈希表、双向链表的头尾哨兵节点、缓存容量：
#include <unordered_map>
#include <iostream>
using namespace std;
struct Node {
int key;
int value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
unordered_map<int, Node*> cache; // 哈希表，key映射到双向链表节点
Node* head; // 链表头哨兵，最近访问的节点放在head后面
Node* tail; // 链表尾哨兵，最久未访问的节点在tail前面
int capacity; // 缓存容量
int size; // 当前缓存大小
// 将节点添加到链表头部（标记为最近使用）
void addToHead(Node* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
// 移除指定节点
void removeNode(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
// 将节点移动到头部
void moveToHead(Node* node) {
removeNode(node);
addToHead(node);
}
// 删除尾部节点（最久未使用）并返回该节点
Node* removeTail() {
Node* node = tail->prev;
removeNode(node);
return node;
}
public:
LRUCache(int cap) : capacity(cap), size(0) {
// 初始化哨兵节点，不存储实际数据
head = new Node(-1, -1);
tail = new Node(-1, -1);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (cache.find(key) == cache.end()) {
return -1; // 不存在返回-1
}
Node* node = cache[key];
moveToHead(node); // 访问后标记为最近使用
return node->value;
}
void put(int key, int value) {
if (cache.find(key) == cache.end()) {
// key不存在，创建新节点
Node* node = new Node(key, value);
cache[key] = node;
addToHead(node);
size++;
if (size > capacity) {
// 容量超出，删除最久未使用的节点
Node* tailNode = removeTail();
cache.erase(tailNode->key);
delete tailNode;
size--;
}
} else {
// key存在，更新值并标记为最近使用
Node* node = cache[key];
node->value = value;
moveToHead(node);
}
}
~LRUCache() {
// 释放所有节点内存
Node* curr = head;
while (curr != nullptr) {
Node* next = curr->next;
delete curr;
curr = next;
}
}
};
// 测试示例
int main() {
LRUCache* lru = new LRUCache(2);
lru->put(1, 1);
lru->put(2, 2);
cout << lru->get(1) << endl; // 返回1
lru->put(3, 3); // 该操作会使得key=2被淘汰
cout << lru->get(2) << endl; // 返回-1
lru->put(4, 4); // 该操作会使得key=1被淘汰
cout << lru->get(1) << endl; // 返回-1
cout << lru->get(3) << endl; // 返回3
cout << lru->get(4) << endl; // 返回4
delete lru;
return 0;
}
实现细节说明
使用哨兵节点可以避免处理链表头尾为空的特殊情况，简化插入和删除的逻辑。哈希表存储key到节点的映射，让get操作可以快速定位到节点，不需要遍历链表。所有操作的时间复杂度都是O(1)，符合缓存高效访问的要求。
在实际使用中，如果缓存的value是复杂对象，需要注意节点的内存管理，避免内存泄漏。如果需要支持泛型，可以将key和value的类型改为模板参数，适配不同的使用场景。