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

class Solution {
private:
    int capacity;
    // 双向链表存储键值对，保持访问顺序，O(1) 时间插入删除
    // int key, int value
    list<pair<int, int>> items;
    // 哈希表 O(1) 时间快速访问
    // int key, iterator value
    unordered_map<int, list<pair<int, int>>::iterator> cache;

public:
    Solution(int capacity) : capacity(capacity) {
        // write code here
    }
 
    int get(int key) {
        // write code here
        auto it = cache.find(key);
        if (it == cache.end()) {
            return -1; // 缓存里没找到
        }
        // 移动到链表头部
        items.splice(items.begin(), items, it->second);
        return it->second->second;
    }
 
    void set(int key, int value){
        // write code here
        auto it = cache.find(key);
        if (it != cache.end()) {
            // 更新值且移动到链表头部
            it->second->second = value;
            items.splice(items.begin(), items, it->second);
            return;
        }

        if (items.size() == capacity) {
            // 达到容量上限了
            auto last = items.back();
            cache.erase(last.first);
            items.pop_back();
        }

        // 在链表头部插入新元素，并在哈希表中存储对应迭代器
        items.emplace_front(key, value);
        cache[key] = items.begin();
    }
};

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