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

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

    int get(int key) {
        if (kv_pair.count(key) == 0)
            return -1;
        else {
            auto it = std::get<0>(kv_pair[key]);
            int val = std::get<1>(kv_pair[key]);
            lru_queue.erase(it);
            lru_queue.push_back(key);
            kv_pair[key] = {std::prev(lru_queue.end()), val};
            return val;
        }
    }

    void set(int key, int value) {
        if (kv_pair.count(key) == 0) {
            lru_queue.push_back(key);
            kv_pair[key] = {std::prev(lru_queue.end()), value};
            if (lru_queue.size() > m_capacity) {
                int key_remove = lru_queue.front();
                kv_pair.erase(key_remove);
                lru_queue.pop_front();
            }
        } else {
            auto it = std::get<0>(kv_pair[key]);
            lru_queue.erase(it);
            lru_queue.push_back(key);
            kv_pair[key] = {std::prev(lru_queue.end()), value};
        }
    }

  private:
    unordered_map<int, pair<list<int>::iterator, int>> kv_pair;
    list<int> lru_queue;
    int m_capacity;
};