题解 | 设计LRU缓存结构

class Solution {
  public:
    Solution(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = mp.find(key);
        if (it == mp.end()) return -1;
        // 移动到表头（最近使用）
        cache.splice(cache.begin(), cache, it->second);
        return it->second->second;
    }

    void set(int key, int value) {
        if (cap == 0) return;
        auto it = mp.find(key);
        if (it != mp.end()) {
            // 已存在，更新并移到表头
            it->second->second = value;
            cache.splice(cache.begin(), cache, it->second);
            return;
        }
        if ((int)cache.size() == cap) {
            // 淘汰表尾
            mp.erase(cache.back().first);
            cache.pop_back();
        }
        cache.emplace_front(key, value);
        mp[key] = cache.begin();
    }

  private:
    int cap;
    list<pair<int, int>> cache; // 链表：表头最新，表尾最旧
    unordered_map<int, list<pair<int, int>>::iterator> mp; // key -> 链表迭代器
};

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