C++ LRU缓存
//构建双向链表的节点结构（要有两个构造函数）
struct Node{
int key, val;
Node* pre;
Node* next;
Node():key(0), val(0), pre(nullptr), next(nullptr) {}
Node(int _key, int _val): key(_key), val(_val), pre(nullptr), next(nullptr) {}
};
class LRUCache {
private:
//哈希表存放key和节点的映射
unordered_map<int, Node*> m;
Node* head;
Node* tail;
int capacity, size;
public:
//LRU构造函数中，设定capacity和size（当前容量）、创建伪头、尾节点并相连
LRUCache(int _capacity) : capacity(_capacity), size(0){
head = new Node();
tail = new Node();
head->next = tail;
tail->pre = head;
}
//取值：如果表里没有这个key，返回-1；如果有，更新节点值，并将其移动至头部
int get(int key) {
if(!m.count(key)) return -1;
Node* node = m[key];
remove(node);
add(node);
return node->val;
}
//放值：如果表里找到，更新值并移动到头部；如果没找到，执行插入操作，插入前先判断是否溢出容量，是的话移除尾部节点，还要将其从表里删除，当前容量减一，然后将新节点加入头部、表、容量加一
void put(int key, int value) {
if(m.count(key)){
Node* node = m[key];
node->val = value;
remove(node);
add(node);
}else{
Node* node = new Node(key, value);
if(size==capacity){
Node* del = tail->pre;
m.erase(del->key);
remove(del);
size--;
}
add(node);
size++;
m[key] = node;
}
}
//删除节点
void remove(Node* node){
node->pre->next = node->next;
node->next->pre = node->pre;
}
//将节点移动至头结点
void add(Node* node){
node->next = head->next;
node->pre = head;
head->next->pre = node;
head->next = node;
}
};