146. LRU 缓存 带TTL的LRU缓存实现(拓展)

LRU缓存

方法一:手动实现双向链表 + 哈希表

struct Node{int val;int key;Node* prev;Node* next;Node(int a, int b): key(a), val(b), prev(nullptr), next(nullptr) {}Node():key(0), val(0), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:Node* removeTail() {Node* node = tail->prev;removeNode(node);return node;}void removeNode(Node* node) {node->next->prev = node->prev;node->prev->next = node->next;}void addToHead(Node* node) {node->next = head->next;node->prev = head;head->next = node;node->next->prev = node;}
public:unordered_map<int, Node*> cache;int size;int capacity;Node* head;Node* tail;LRUCache(int capacity) {this->capacity = capacity;size = 0;head = new Node();tail = new Node();head->next = tail;tail->prev = head;}int get(int key) {if(!cache.count(key)) {return -1;}Node* node = cache[key];removeNode(node);addToHead(node);return node->val;}void put(int key, int value) {if(!cache.count(key)) {Node* node = new Node(key, value);addToHead(node);++size;cache[key] = node;if(size > capacity) {Node* removed = removeTail();cache.erase(removed->key);--size;delete removed;}} else {Node* node = cache[key];node->val = value;removeNode(node);addToHead(node);}}
};

拓展

实现带TTL的LRU缓存
要求:
在本题的基础上，为 key 增加过期时间（put 调用时额外传入过期时间）。如果 key 过期，则需要删除掉。

#include <unordered_map>
#include <chrono>using namespace std;
using namespace std::chrono;struct Node {int val;int key;Node* prev;Node* next;time_point<steady_clock> timestamp; // 时间戳，记录节点插入或更新时间Node(int a, int b) : key(a), val(b), prev(nullptr), next(nullptr) {timestamp = steady_clock::now(); // 初始化时间戳}Node() : key(0), val(0), prev(nullptr), next(nullptr) {timestamp = steady_clock::now(); // 初始化时间戳}
};class LRUCache {
private:Node* removeTail() {Node* node = tail->prev;removeNode(node);return node;}void removeNode(Node* node) {node->next->prev = node->prev;node->prev->next = node->next;}void addToHead(Node* node) {node->next = head->next;node->prev = head;head->next = node;node->next->prev = node;}bool isExpired(Node* node, int ttl) {auto now = steady_clock::now();auto duration = duration_cast<milliseconds>(now - node->timestamp).count();return duration > ttl; // 如果超过TTL，则认为已过期}public:unordered_map<int, Node*> cache;int size;int capacity;int ttl; // TTL时间，单位为毫秒Node* head;Node* tail;LRUCache(int capacity, int ttl) : capacity(capacity), ttl(ttl) {size = 0;head = new Node();tail = new Node();head->next = tail;tail->prev = head;}int get(int key) {if (!cache.count(key)) {return -1;}Node* node = cache[key];// 检查是否过期if (isExpired(node, ttl)) {removeNode(node);cache.erase(key);--size;delete node;return -1;}// 更新节点时间戳node->timestamp = steady_clock::now();removeNode(node);addToHead(node);return node->val;}void put(int key, int value) {if (!cache.count(key)) {Node* node = new Node(key, value);// 如果缓存已满，移除最久未使用的节点if (size >= capacity) {Node* removed = removeTail();cache.erase(removed->key);--size;delete removed;}// 插入新节点addToHead(node);cache[key] = node;++size;} else {Node* node = cache[key];node->val = value;// 检查是否过期if (isExpired(node, ttl)) {removeNode(node);cache.erase(key);--size;delete node;put(key, value); // 重新插入return;}// 更新节点时间戳node->timestamp = steady_clock::now();removeNode(node);addToHead(node);}}
};

总结:
在原代码基础上为每一个steady_lock的timestamp时间戳, 每次get或者put已有Node时进行检测isExpired,如果检测已经过期则对get删除节点, 对put更新时间戳