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) 时间复杂度，适合高频访问场景。注意手动管理内存或可改用智能指针。基本上就这些，不复杂但容易忽略细节比如指针连接顺序和析构处理。