LRU缓存

struct Node{

    int key;

    int value;

    Node* next;

    Node* pre;

    Node():

            key(-1), value(-1), next(nullptr), pre(nullptr){}

    explicit Node(int key_, int val_):

            key(key_), value(val_), next(nullptr), pre(nullptr){}

    Node(int key_, int val_, Node* next_, Node* pre_):

            key(key_), value(val_),next(next_), pre(pre_){}

};

class LRUCache {

public:

    explicit LRUCache(int capacity):

    capacity(capacity){

        size = 0; //初始值设为0

        head = new Node();

        tail = new Node();

        head -> next = tail;

        tail -> pre = head;

    }

    int get(int key) {

        if(hashMap.end() == hashMap.find(key)){

            return -1;

        }

        auto cur = hashMap[key];

        int val = cur -> value;

        int key_ = cur -> key;

        erase(cur);

        cur = new Node(key_, val);

        insert(cur);

        return val;

    }

    void put(int key, int value) {

        if(hashMap.end() != hashMap.find(key)){

            auto cur = hashMap[key];

            int val = value;

            int key_ = cur -> key;

            erase(cur);

            cur = new Node(key_, val);

            hashMap[key] = cur;

            insert(cur);

        }else{

            auto cur = new Node(key, value);

            if(size < capacity){

                hashMap[key] = cur;

                size++;

            }else{

                auto lastNode = tail -> pre;

                hashMap.erase(lastNode->key);

                hashMap[key] = cur;

                erase(lastNode);

            }

            insert(cur);

        }

    }

    void erase(Node *node){

        if( node -> pre != nullptr && node -> next != nullptr){

            Node *pre = node -> pre;

            Node *next = node -> next;

            pre -> next = next;

            next -> pre = pre;

            node -> pre = nullptr;

            node -> next = nullptr;

            delete(node);

            node = nullptr;

        }

    }

    void insert(Node *node){

        Node *next = head -> next;

        head -> next = node;

        next -> pre = node;

        node -> pre = head;

        node -> next = next;

    }

private:

    Node *head;

    Node *tail;

    unordered_map<int, Node*> hashMap;

    int capacity;

    int size;

};
巴特西

LRU缓存

LRU缓存

最新文章

热门文章
