LRU即最近最少使用，是一种常见的缓存淘汰策略，当缓存容量达到上限时，会优先移除最久没有被访问的数据。在C++中实现高效的LRU缓存系统，通常需要结合双向链表和哈希表，这里选择unordered_map来优化查询效率，避免单纯使用链表带来的遍历开销。
LRU缓存系统设计思路
整体设计分为两个核心部分：
- 双向链表：用来维护节点的访问顺序，链表头部是最近访问的节点，尾部是最久未访问的节点，容量满时直接移除尾部节点即可。
- unordered_map：键为缓存的键，值为双向链表节点的指针，通过哈希表可以在O(1)时间内定位到对应节点，避免链表的线性查询。
节点结构设计
双向链表的节点需要存储键、值、前驱指针和后继指针，方便后续的插入、删除操作，节点定义如下：
// 双向链表节点定义
struct Node {
int key; // 缓存键
int value; // 缓存值
Node* prev; // 前驱节点指针
Node* next; // 后继节点指针
// 构造函数
Node(int k = 0, int v = 0) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
LRU缓存类核心成员
LRU缓存类需要维护容量、哈希表、双向链表的头尾哑节点，哑节点可以简化边界条件的处理，不需要额外判断头尾节点为空的情况：
#include <unordered_map>
#include <iostream>
class LRUCache {
private:
int capacity; // 缓存容量
std::unordered_map<int, Node*> cacheMap; // 哈希表，键到链表节点的映射
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();
tail = new Node();
head->next = tail;
tail->prev = head;
}
};
核心操作实现
get操作
get操作的逻辑是：先通过unordered_map查询键是否存在，如果不存在返回-1；如果存在，说明该节点被访问了，需要将其移动到链表头部，然后返回值。
int get(int key) {
// 查询哈希表
auto it = cacheMap.find(key);
if (it == cacheMap.end()) {
// 键不存在，返回-1
return -1;
}
// 键存在，将节点移动到头部表示最近访问
Node* node = it->second;
moveToHead(node);
return node->value;
}
put操作
put操作的逻辑是：先查询键是否存在，如果存在，更新值并移动到头部；如果不存在，创建新节点插入头部，同时加入哈希表，如果容量超过上限，移除尾部节点并从哈希表中删除对应的键。
void put(int key, int value) {
auto it = cacheMap.find(key);
if (it != cacheMap.end()) {
// 键已存在，更新值并移动到头部
Node* node = it->second;
node->value = value;
moveToHead(node);
} else {
// 键不存在，创建新节点
Node* newNode = new Node(key, value);
// 插入到头部
addToHead(newNode);
// 加入哈希表
cacheMap[key] = newNode;
// 判断容量是否超限
if (cacheMap.size() > capacity) {
// 移除尾部最久未访问的节点
Node* tailNode = removeTail();
// 从哈希表中删除对应的键
cacheMap.erase(tailNode->key);
// 释放节点内存
delete tailNode;
}
}
}
完整测试代码
以下是完整的可运行测试代码，验证缓存的功能是否符合预期：
int main() {
LRUCache* lruCache = new LRUCache(2);
lruCache->put(1, 1);
lruCache->put(2, 2);
std::cout << lruCache->get(1) << std::endl; // 返回1，访问后1变为最近使用
lruCache->put(3, 3); // 容量满，移除最久未访问的2
std::cout << lruCache->get(2) << std::endl; // 返回-1，2已被移除
lruCache->put(4, 4); // 容量满，移除最久未访问的1
std::cout << lruCache->get(1) << std::endl; // 返回-1，1已被移除
std::cout << lruCache->get(3) << std::endl; // 返回3
std::cout << lruCache->get(4) << std::endl; // 返回4
return 0;
}
性能说明
这种实现方式下，get、put操作的时间复杂度都是O(1)，因为unordered_map的查询、插入、删除平均时间复杂度是O(1)，双向链表的插入、删除操作也是O(1)，避免了单纯使用双向链表时查询需要遍历O(n)的问题，适合对缓存性能要求较高的场景。
注意事项
- 哑节点的使用可以大幅简化边界处理，不需要判断链表为空或者操作头尾节点的特殊情况。
- 节点删除时要同步释放内存，避免内存泄漏，同时要记得从unordered_map中移除对应的键。
- 如果缓存存储的是大对象，节点的值可以改为指针或者智能指针，减少拷贝开销。
LRU_cacheunordered_map双向链表C++修改时间：2026-06-24 23:33:41