LRU

LRU（Least Recently Used）最近最少使用算法

#include <unordered_map>
#include <deque>
#include <queue>
using namespace std;
struct Node
{
    int key, val;
    Node* prve, *next;
    Node() : key(0), val(0), prve(nullptr), next(nullptr) {};
    Node(int _key, int _val) : key(_key), val(_val), prve(nullptr), next(nullptr) {};
};

class LRUCache
{
public:
    LRUCache(int _capacity) : capacity_(_capacity), current_size_(0)
    {
        head_ = new Node();
        tail_ = new Node();
        head_->next = tail_;
        tail_->prve = head_;
    }
    ~LRUCache();

    void RemoveNode(Node* node)
    {
        node->prve->next = node->next;
        node->next->prve = node->prve;
        //delete node;
    }

    void AddNode(Node* node)
    {
        node->next = head_->next;
        head_->next->prve = node;
        node->prve = head_;
        head_->next = node;
    }

    int GetVal(int key)
    {
        if (!date_.count(key)) return -1;
        Node* node = date_[key];
        RemoveNode(node);
        AddNode(node);
        return node->val;
    }

    void PutNode(int key, int val)
    {
        if (date_.count(key))
        {
            Node* node = date_[key];
            node->val = val;
            RemoveNode(node);
            AddNode(node);
        }
        else
        {
            if (current_size_ == capacity_)
            {
                Node* remove_node = tail_->prve;
                RemoveNode(remove_node);
                date_.erase(remove_node->key);
                current_size_--;
            }
            Node* node = new Node(key, val);
            AddNode(node);
            date_[key] = node;
            current_size_++;
        }
    }

private:
    Node* head_, * tail_;
    unordered_map<int, Node*> date_;
    int capacity_, current_size_;
};