最近最少使用算法（LRU）是操作系统中内存页面调度和分布式系统中缓存淘汰的常用策略，核心逻辑是当缓存空间不足时，优先淘汰最久没有被访问过的缓存数据。在C++中实现LRU缓存，需要同时维护数据的访问顺序和快速的查询、插入、删除能力。
LRU算法核心设计思路
要实现高效的LRU缓存，需要满足以下操作的时间复杂度尽可能低：
- 查询缓存数据：O(1)时间复杂度
- 插入新的缓存数据：O(1)时间复杂度
- 淘汰最久未访问的数据：O(1)时间复杂度
单独使用哈希表可以实现O(1)的查询，但无法维护访问顺序；单独使用链表可以维护顺序，但查询需要O(n)时间。因此最优的组合是使用哈希表+双向链表：
- 哈希表存储键到双向链表节点的映射，实现快速查询
- 双向链表按访问时间排序，头部是最新访问的节点，尾部是最久未访问的节点
数据结构定义
首先定义双向链表的节点结构，每个节点存储缓存的键、值，以及前驱和后继指针：
// 双向链表节点定义
struct LRU_Node {
int key;
int value;
LRU_Node* prev;
LRU_Node* next;
LRU_Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
然后定义LRU缓存类，包含缓存容量、哈希表、双向链表的头尾虚拟节点：
#include <unordered_map>
#include <iostream>
class LRU_Cache {
private:
int capacity; // 缓存最大容量
std::unordered_map<int, LRU_Node*> cache_map; // 键到链表节点的映射
LRU_Node* head; // 虚拟头节点，指向最新访问的节点
LRU_Node* tail; // 虚拟尾节点，指向最久未访问的节点
// 将节点移动到链表头部（表示最新访问）
void move_to_head(LRU_Node* node) {
if (node == head->next) return; // 已经是头节点，无需移动
// 先移除节点原有位置
remove_node(node);
// 插入到头节点之后
add_to_head(node);
}
// 移除指定节点
void remove_node(LRU_Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
// 将节点插入到头节点之后
void add_to_head(LRU_Node* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
// 移除链表尾部节点（最久未访问）
LRU_Node* remove_tail() {
LRU_Node* node = tail->prev;
remove_node(node);
return node;
}
public:
// 构造函数，初始化缓存容量和虚拟头尾节点
LRU_Cache(int cap) : capacity(cap) {
head = new LRU_Node(-1, -1);
tail = new LRU_Node(-1, -1);
head->next = tail;
tail->prev = head;
}
// 析构函数，释放所有节点内存
~LRU_Cache() {
LRU_Node* curr = head;
while (curr != nullptr) {
LRU_Node* next = curr->next;
delete curr;
curr = next;
}
}
};
核心操作实现
查询缓存数据
查询时先通过哈希表判断键是否存在，如果不存在返回-1；如果存在，将对应节点移动到链表头部表示最新访问，再返回值：
int get(int key) {
// 键不存在，返回-1
if (cache_map.find(key) == cache_map.end()) {
return -1;
}
// 键存在，将节点移动到头部，返回值
LRU_Node* node = cache_map[key];
move_to_head(node);
return node->value;
}
插入缓存数据
插入时先判断键是否存在：如果已存在，更新值并将节点移动到头部；如果不存在，创建新节点插入头部，同时加入哈希表，如果超过容量则淘汰尾部节点：
void put(int key, int value) {
if (cache_map.find(key) != cache_map.end()) {
// 键已存在，更新值并移动到头部
LRU_Node* node = cache_map[key];
node->value = value;
move_to_head(node);
} else {
// 键不存在，创建新节点
LRU_Node* new_node = new LRU_Node(key, value);
// 加入哈希表
cache_map[key] = new_node;
// 插入到链表头部
add_to_head(new_node);
// 超过容量，淘汰尾部节点
if (cache_map.size() > capacity) {
LRU_Node* tail_node = remove_tail();
cache_map.erase(tail_node->key);
delete tail_node;
}
}
}
完整测试示例
以下代码测试LRU缓存的基本功能：
int main() {
LRU_Cache* lru_cache = new LRU_Cache(2); // 缓存容量为2
lru_cache->put(1, 1); // 缓存是 {1=1}
lru_cache->put(2, 2); // 缓存是 {1=1, 2=2}
std::cout << lru_cache->get(1) << std::endl; // 返回1，缓存变为 {2=2, 1=1}
lru_cache->put(3, 3); // 淘汰键2，缓存变为 {1=1, 3=3}
std::cout << lru_cache->get(2) << std::endl; // 返回-1，键2不存在
lru_cache->put(1, 10); // 更新键1的值，缓存变为 {3=3, 1=10}
std::cout << lru_cache->get(1) << std::endl; // 返回10
std::cout << lru_cache->get(3) << std::endl; // 返回3
delete lru_cache;
return 0;
}
复杂度分析
该实现的各项操作复杂度如下：
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| get查询 | O(1) | O(1) |
| put插入/更新 | O(1) | O(1) |
| 整体缓存 | - | O(capacity) |
这种实现方式兼顾了查询效率和顺序维护的需求，适合大多数需要LRU缓存的场景，比如数据库查询缓存、接口返回结果缓存等。如果需要对缓存数据做持久化或者分布式同步，可以在此基础上扩展对应的逻辑。