LRU缓存即最近最少使用缓存，是一种常见的缓存淘汰策略，当缓存容量达到上限时，会优先移除最久未被访问的数据。用C++实现简单LRU缓存时，结合双向链表和unordered_map是非常高效的方案，双向链表维护数据的访问顺序，unordered_map加速键到链表节点的查找。
核心设计思路
整个LRU缓存的结构由两部分组成：
- 双向链表：每个节点存储缓存的键、值，以及前驱和后继指针。链表头部是最近访问的数据，尾部是最久未访问的数据，容量满时直接删除尾部节点。
- unordered_map：键为缓存的键，值为对应双向链表节点的指针，这样查找某个键是否存在时不需要遍历链表，时间复杂度为O(1)。
节点结构定义
首先定义双向链表的节点结构，包含键、值、前驱和后继指针：
struct Node {
int key;
int value;
Node* prev;
Node* next;
// 构造函数，初始化节点内容
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
LRU缓存类实现
LRU缓存类需要维护链表头尾的哑节点，方便插入和删除操作，同时维护unordered_map和缓存容量：
#include <unordered_map>
#include <iostream>
class LRUCache {
private:
int capacity; // 缓存容量
std::unordered_map<int, Node*> cache; // 键到链表节点的映射
Node* head; // 链表头哑节点，指向最近访问的节点
Node* tail; // 链表尾哑节点，指向最久未访问的节点
// 将节点移动到链表头部，表示最近访问
void moveToHead(Node* node) {
// 先移除节点原来的位置
removeNode(node);
// 插入到头部
addToHead(node);
}
// 移除指定节点
void removeNode(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
// 将节点插入到链表头部
void addToHead(Node* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
// 删除链表尾部节点，即最久未访问的节点
Node* removeTail() {
Node* node = tail->prev;
removeNode(node);
return node;
}
public:
// 构造函数，初始化容量和哑节点
LRUCache(int cap) : capacity(cap) {
head = new Node(-1, -1);
tail = new Node(-1, -1);
head->next = tail;
tail->prev = head;
}
// 析构函数，释放所有节点内存
~LRUCache() {
Node* cur = head;
while (cur != nullptr) {
Node* tmp = cur;
cur = cur->next;
delete tmp;
}
}
// 获取缓存值，如果存在则移动到头部，不存在返回-1
int get(int key) {
if (cache.find(key) == cache.end()) {
return -1;
}
Node* node = cache[key];
moveToHead(node);
return node->value;
}
// 插入或更新缓存
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
// 键已存在，更新值并移动到头部
Node* node = cache[key];
node->value = value;
moveToHead(node);
} else {
// 键不存在，创建新节点
Node* newNode = new Node(key, value);
// 插入到映射表和链表头部
cache[key] = newNode;
addToHead(newNode);
// 如果超过容量，删除尾部节点
if (cache.size() > capacity) {
Node* tailNode = removeTail();
cache.erase(tailNode->key);
delete tailNode;
}
}
}
};
使用示例
下面是简单的测试代码，验证LRU缓存的功能：
int main() {
LRUCache lru(2); // 缓存容量为2
lru.put(1, 1); // 缓存是 {1=1}
lru.put(2, 2); // 缓存是 {2=2, 1=1}，2是最近访问的
std::cout << lru.get(1) << std::endl; // 返回1，缓存变为 {1=1, 2=2}
lru.put(3, 3); // 容量满，淘汰2，缓存变为 {3=3, 1=1}
std::cout << lru.get(2) << std::endl; // 2已被淘汰，返回-1
lru.put(1, 100); // 更新键1的值，缓存变为 {1=100, 3=3}
std::cout << lru.get(1) << std::endl; // 返回100
return 0;
}
实现要点说明
这里使用头尾哑节点是为了避免插入删除时对空指针做特殊处理，简化代码逻辑。所有操作的时间复杂度都是O(1)：get操作通过unordered_map找到节点后移动到头部，put操作插入或更新后如果超容就删除尾部节点，整体效率很高。如果需要存储其他类型的值，可以把节点的value类型改成模板参数，适配更多使用场景。
LRU缓存双向链表unordered_mapC++缓存实现修改时间：2026-06-09 11:21:34