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

#include <unordered_map>
class Solution {
    using kv = pair<int, int>; // <key, value>
    int capacity;
    list<kv> lis;
    unordered_map<int, list<kv>::iterator> keyToPtr;

    // 将指针指向的节点移动到链表头部，并更新指针信息
    void MoveToHead(list<kv>::iterator &p) {
        lis.push_front(*p);
        lis.erase(p);
        p = lis.begin();
    }

    void Insert() {

    }

  public:
    Solution(int capacity): capacity(capacity) {
        // write code here
    }

    int get(int key) {
        // write code here
        if (keyToPtr.count(key) == 0) return -1;
        MoveToHead(keyToPtr[key]);
        return keyToPtr[key]->second;
    }

    void set(int key, int value) {
        // write code here
        if (keyToPtr.count(key) == 0) { // 没有这个 key，插入
            if (lis.size() == capacity) { // 容量满了，删除最久没有访问的
                keyToPtr.erase(lis.back().first);
                lis.pop_back();
            }
            lis.push_front({key, value});
            keyToPtr[key] = lis.begin();
        } else { // 有这个 key，更新
            MoveToHead(keyToPtr[key]);
            keyToPtr[key]->second = value;
        }
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* solution = new Solution(capacity);
 * int output = solution->get(key);
 * solution->set(key,value);
 */