当前位置：首页 > news >正文

LRU缓存C++

news 2025/6/27 11:06:47

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1，并将1节点放到最上方
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

class Node{
public:int key;int value;// 双链表，节约查找时间Node* pre;Node* next;Node(int k=0, int v=0):key(k), value(v){}
};class LRUCache {
private:int capacity;  Node* dummy;     // 哨兵节点unordered_map<int, Node*> key_to_node;    // 建立key到节点的映射// 删除一个节点(双链表的删除操作)void remove(Node* x){x->pre->next = x->next;x->next->pre = x->pre;}// 在链表头添加一个节点(双链表的添加操作)void push_front(Node* x){x->pre=dummy;x->next = dummy->next;x->pre->next = x;x->next->pre = x;}// 获取key对应节点，把该节点移到链表头部Node* get_node(int key){auto it = key_to_node.find(key);if(it == key_to_node.end())  // 没找到{return nullptr;}Node* node = it->second;remove(node);   // 在原位置删掉push_front(node);   // 在新位置添加return node;}
public:LRUCache(int capacity):capacity(capacity), dummy(new Node()) {// 初始化双链表dummy->pre = dummy;dummy->next = dummy;}int get(int key) {Node* node = get_node(key);// 没找到返回-1return node?node->value:-1;}void put(int key, int value) {Node* node=get_node(key);// 先找是否在链表中，若在链表中则更新value的值if(node){node->value = value;return;}// 若不在链表中，则创建一个新的节点，插入node = new Node(key, value);key_to_node[key] = node;push_front(node);// 若插入后大于了总容量，则删掉一个结点if(key_to_node.size() > capacity){Node* back_node = dummy->pre;key_to_node.erase(back_node->key);remove(back_node);delete back_node;}}
};