LRU缓存通过哈希表+双向链表实现O(1)操作，最近访问节点置于链表头部，满时淘汰尾部节点。
LRU（Least Recently Used）缓存淘汰算法的核心思想是：当缓存满时，优先淘汰最久未使用的数据。在C++中，可以通过哈希表 + 双向链表高效实现O(1)的插入、查找和删除操作。
基本数据结构设计
使用std::unordered_map存储键到节点指针的映射，双向链表维护访问顺序——最近使用的放头部，淘汰从尾部进行。
定义链表节点结构：
struct ListNode {int key, value;
ListNode* prev;
ListNode* next;
ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
核心操作实现
封装LRUCache类，包含以下关键函数：
立即学习“C++免费学习笔记（深入）”；
- get(int key)：若存在，将对应节点移到链表头并返回值；否则返回-1
- put(int key, int value)：新增或更新键值对，若超出容量则删除尾节点
辅助方法用于维护链表：
- removeNode(ListNode* node)：从链表中移除指定节点
- addToHead(ListNode* node)：将节点插入链表头部
完整代码示例
class LRUCache {private:
std::unordered_map
ListNode* head;
ListNode* tail;
int capacity;
void removeNode(ListNode* node) {
if (node == head) head = node->next;
if (node == tail) tail = node->prev;
if (node->prev) node->prev->next = node->next;
if (node->next) node->next->prev = node->prev;
}
void addToHead(ListNode* node) {
node->next = head;
node->prev = nullptr;
if (head) head->prev = node;
head = node;
if (!tail) tail = node;
}
public:
LRUCache(int cap) : capacity(cap), head(nullptr), tail(nullptr) {}
int get(int key) {
if (cache.find(key) == cache.end()) return -1;
ListNode* node = cache[key];
removeNode(node);
addToHead(node);
return node->value;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
ListNode* node = cache[key];
node->value = value;
removeNode(node);
addToHead(node);
} else {
ListNode* newNode = new ListNode(key, value);
cache[key] = newNode;
addToHead(newNode);
if (cache.size() > capacity) {
ListNode* toDelete = tail;
removeNode(tail);
cache.erase(toDelete->key);
delete toDelete;
}
}
}
};
注意：实际项目中可考虑智能指针管理内存，避免手动new/delete。这个实现保证了get和put操作均摊时间复杂度为O(1)，符合高频访问场景需求。
基本上就这些。
