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

#include <list>
#include <unordered_map>
class Solution {
    using List = list<pair<int, int>>;
    List lists;
    unordered_map<int, List::iterator> hash;
    int size;
public:
    Solution(int capacity){
        size = capacity;
    }
 
    int get(int key) {
        if (hash.count(key)) {
            int res = (*(hash[key])).second;
            lists.erase(hash[key]);
            lists.emplace_front(key, res);
            hash[key] = lists.begin();
            return res;
        } else {
            return -1;
        }
    }
 
    void set(int key, int value){
        if (hash.count(key)) {
            lists.erase(hash[key]);
        }
        lists.emplace_front(key, value);
        hash[key] = lists.begin();
        if (lists.size() > size) {
            int erase_key = lists.back().first;
            lists.erase(hash[erase_key]);
            hash.erase(erase_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);
 */

思路：

* 双向链表表示k-v插入的顺序。

* 哈希表根据key在常数时间内找到双向链表中对应的位置。