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

由于插入复杂度要求为O(1)，所以要用链表，stl中的list就可以，不用再重新建立链表的数据结构。

然后读取的复杂度也要为O(1)，所以为了确定位置，需要利用到哈希表，哈希表对应的值就是list迭代器的位置，因为list的迭代器不会因为其他元素的删除而改变。

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        vector<int> res;
        for(auto op : operators){
            if(op.size() == 3) _set(op[1], op[2], k);
            else res.push_back(_get(op, k));
        }
        return res;
    }
private:
    list<pair<int, int> > li; // {key, value}
    unordered_map<int, list<pair<int, int> >::iterator> hs;
    
    void _set(int key, int value, int k){
        if(hs.find(key) == hs.end()){ // key不存在
            if(li.size() == k){ // 满了，删除列表第一个
                hs.erase(li.front().first);//哈希表中根据key删除
                li.erase(li.begin());//列表中根据迭代器删除
            }
        }else{ // key存在，列表直接删除key对应的迭代器位置
            li.erase(hs[key]); 
            hs.erase(key);
        }
        // 重新插入
        li.push_back({key, value});
        hs[key] = prev(li.end());
    }
    
    int _get(vector<int> &op, int k){
        int key = op[1];
        if(hs.find(key) == hs.end()) return -1; // 不存在返回-1
        int value = hs[key]->second;// 存在相当于再set一下
        _set(key, value, k);
        return value;
    }
};