LRU算法实现

介绍

LRU算法（最近最少使用）是最常用的缓存回收算法。主要的实现方式就是带哈希表的双向链表。

• 哈希能够帮我们快速定位我们需要的缓存页面
• 双向链表提供的顺序性能够让我们选择回收最少使用的页面。
• 双向链表可以在任意节点插入，便于移动缓存页面的顺序。

代码

/**
 * @file LRU.cpp
 * @author qingfu
 * @brief a implement of LRUcache 
 * @version 0.1
 * @date 2021-04-05
 * 
 * @copyright Copyright (c) 2021
 * 
 */
#include <unordered_map>
#include <iostream>

using namespace std;

struct Node {
    int key,val;
    Node *prev,*next;
    Node():key(-1),val(-1),prev(nullptr),next(nullptr){}
    Node(int k,int v):key(k),val(v),prev(nullptr),next(nullptr) {}
};

class LRUCache{
public:
    LRUCache()=delete;
    LRUCache(const int capacity):_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];
        moveTohead(node);
        return node->val;

    }
    void put(int key,int value){

        if(_cache.count(key)){
            Node *node=_cache[key];
            node->val=value;
            moveTohead(node);
        }
        else{
            Node *node=new Node(key,value);
            addToHead(node);
            _cache[key]=node;
            _size++;
            if(_size>_capacity){
                Node *removed=removeFromTail();
                _cache.erase(removed->key);
                delete removed;
                _size--;
            }
        }
    }

private:
    void addToHead(Node *node){
        _head->next->prev=node;
        node->next=_head->next;
        _head->next=node;
        node->prev=_head;
    }
    Node* removeFromTail(){
        Node *pre=_tail->prev;
        remove(pre);

        return pre;
    }
    void remove(Node *node){
        node->prev->next=node->next;
        node->next->prev=node->prev;
        node->prev=nullptr;
        node->next=nullptr;
    }
    void moveTohead(Node *node){
        remove(node);
        addToHead(node);
    }

private:
    Node *_head;
    Node *_tail;
    int _size;
    const int _capacity;
    unordered_map<int,Node*> _cache;
};

int main(){
    LRUCache *cache=new LRUCache(4);
    cache->put(1,2);
    cache->put(3,4);
    cache->put(5,6);
    cache->put(7,8);
    cout<<cache->get(1)<<endl;
    cout<<cache->get(3)<<endl;
    cout<<cache->get(5)<<endl;
    cout<<cache->get(7)<<endl;
    cout<<cache->get(9)<<endl;
    cache->put(1,0);
    cout<<cache->get(1)<<endl;
    cache->put(9,10);
    cout<<cache->get(3)<<endl;
    cout<<cache->get(9)<<endl;

    return 0;



}