LRU缓存通过哈希表和双向链表实现，get和put操作均O(1)：访问时移至链表头，满时删尾部节点。
实现一个LRU（Least Recently Used）缓存淘汰算法，核心是结合哈希表和双向链表，做到查询和更新都在 O(1) 时间完成。C++ 中可以通过 unordered_map 和自定义的双向链表节点来高效实现。
基本思路
LRU 缓存需要满足：
- 访问某个键时，它变为“最近使用”
- 当缓存满时，淘汰最久未使用的项
- get 和 put 操作都需在 O(1) 完成
为此，我们使用：
- unordered_map：快速查找 key 是否存在，以及对应节点位置
- 双向链表：维护使用顺序，头结点是最新的，尾结点是最老的
数据结构设计
定义双向链表节点和缓存类框架：
立即学习“C++免费学习笔记（深入）”；
struct Node {
int key, value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
缓存类包含：
- 容量 capacity
- 当前大小 size
- 哈希表 map
- 伪头部和伪尾部简化边界处理
关键操作实现
封装两个辅助函数：
void removeNode(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
<p>void addToHead(Node* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}</p>get 操作逻辑：
- 查 map 是否存在 key
- 不存在返回 -1
- 存在则将其移到链表头部（表示最近使用），并返回值
put 操作逻辑：
- 如果 key 已存在，更新值并移到头部
- 如果不存在，新建节点插入头部
- 若超出容量，删除尾部节点（最久未使用）及 map 中对应项
完整代码示例
#include <unordered_map>
using namespace std;
<p>class LRUCache {
private:
struct Node {
int key, value;
Node<em> prev;
Node</em> next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};</p><pre class='brush:php;toolbar:false;'>int capacity;
unordered_map<int, Node*> cache;
Node* head;
Node* tail;
void removeNode(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void addToHead(Node* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
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(0, 0); tail = new Node(0, 0); head->next = tail; tail->prev = head; }
int get(int key) {
auto it = cache.find(key);
if (it == cache.end()) return -1;
Node* node = it->second;
moveToHead(node);
return node->value;
}
void put(int key, int value) {
auto it = cache.find(key);
if (it != cache.end()) {
Node* node = it->second;
node->value = value;
moveToHead(node);
} else {
Node* newNode = new Node(key, value);
cache[key] = newNode;
addToHead(newNode);
if (cache.size() > capacity) {
Node* removed = removeTail();
cache.erase(removed->key);
delete removed;
}
}
}
~LRUCache() {
Node* curr = head;
while (curr) {
Node* temp = curr;
curr = curr->next;
delete temp;
}
}};
这个实现保证了 get 和 put 都是 O(1) 时间复杂度，适合高频访问场景。注意手动管理内存或可改用智能指针。基本上就这些，不复杂但容易忽略细节比如指针连接顺序和析构处理。
