题解 | #设计LRU缓存结构#

#include <map>

struct MyListNode {
    MyListNode *pre = nullptr;
    MyListNode *next = nullptr;
    int key;
    int value;
public:
    MyListNode(int k, int v) : key(k), value(v) {}
    MyListNode() {}
};

class Solution {
private:
    int cap;
    MyListNode *hair;
    MyListNode *tair;
    std::map<int, MyListNode*> map;
    void refresh(MyListNode *current) {
        MyListNode *pre = current->pre;
        MyListNode *next = current->next;
        if (pre != nullptr) {
            pre->next = next;
        }
        if (next != nullptr) {
            next->pre = pre;
        }

        MyListNode *tailPre = tair->pre;
        tailPre->next = current;
        current->pre = tailPre;
        current->next = tair;
        tair->pre = current;
    }
public:
    Solution(int capacity) : cap(capacity), hair(new MyListNode()), tair(new MyListNode()){
        hair->next = tair;
        tair->pre = hair;
    }

    int get(int key) {
        // write code here
        if (map.find(key) == map.end()) {
            return -1;
        }
        MyListNode *current = map.find(key)->second;
        refresh(current);
        MyListNode *p = hair->next;
        while (p != tair) {
            std::cout << p->key << ":" << p->value << " ";
            p = p->next;
        }
        return current->value;
    }

    void set(int key, int value){
        // write code here
        if (map.find(key) != map.end()) {
            MyListNode *current = map.find(key)->second;
            current->value = value;
            refresh(current);
        } else {
            auto *listNode = new MyListNode(key, value);
            if (map.size() >= this->cap) {
                MyListNode *del = hair->next;
                MyListNode *next = del->next;
                hair->next = next;
                next->pre = hair;
                map.erase(del->key);
            }
            map.insert({key, listNode});
            refresh(listNode);
        }
        MyListNode *p = hair->next;
    }
};