答案：LRU缓存通过哈希表和双向链表实现，支持O(1)查找、插入与删除，访问或添加节点时移至链表头部，容量超限时删除尾部最久未使用节点。
实现一个LRU（Least Recently Used）缓存，核心在于快速访问数据的同时维护访问顺序，当缓存满时淘汰最久未使用的项。C++中可以通过结合哈希表和双向链表高效实现。
LRU缓存的基本原理
LRU缓存要求：
- 支持O(1)时间的插入、查找和删除操作。
- 每次访问某个键值后，将其标记为“最近使用”。
- 当容量超限时，自动删除最久未使用的条目。
为了满足这些需求，通常采用：
- std::unordered_map：用于存储键到节点的映射，实现快速查找。
- 自定义双向链表：维护访问顺序，头结点是最新的，尾结点是最旧的。
设计双向链表节点结构
每个缓存项需要保存键、值，并能前后连接：
立即学习“C++免费学习笔记（深入）”；
struct Node {
int key, value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
这个结构便于在链表中快速移动或删除节点。
LRUCache类的实现
完整类定义包括初始化、获取、插入等操作：
class LRUCache {
private:
int capacity;
std::unordered_map cache;
Node* head; // 指向最新使用的节点
Node* tail; // 指向最久未使用的节点
// 将现有节点移到链表头部
void moveToHead(Node* node) {
if (node == head) return;
if (node == tail) {
tail = tail->prev;
tail->next = nullptr;
} else {
node->prev->next = node->next;
node->next->prev = node->prev;
}
node->prev = nullptr;
node->next = head;
head->prev = node;
head = node;
}
// 添加新节点到头部
void addToHead(Node* node) {
node->next = head;
node->prev = nullptr;
if (head) head->prev = node;
head = node;
if (!tail) tail = node;
}
// 删除尾部节点（最久未使用）
void removeTail() {
if (!tail) return;
Node* toDel = tail;
tail = tail->prev;
if (tail) tail->next = nullptr;
else head = nullptr;
cache.erase(toDel->key);
delete toDel;
}public:
LRUCache(int cap) : capacity(cap), head(nullptr), tail(nullptr) {}
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()) {
cache[key]->value = value;
moveToHead(cache[key]);
} else {
Node* newNode = new Node(key, value);
if (cache.size() >= capacity) {
removeTail();
}
addToHead(newNode);
cache[key] = newNode;
}
}};
使用示例与注意事项
测试代码：
int main() {
LRUCache lru(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（已淘汰）
return 0;
}
注意点：
- 指针操作要小心，避免内存泄漏或野指针。
- 边界情况如空链表、单节点需正确处理。
- C++11以上可用智能指针进一步提升安全性，但会略微影响性能。
基本上就这些。用哈希表加双向链表的方式，既能保证查找效率，又能维护访问顺序，是实现LRU的经典做法。
