LRU缓存结构(哈希表+链表)

/*
set(key,value) 和 get(key) 时间复杂度为O(1)
查找复杂度为O(1)用哈希表unordered_map，插入删除为O(1)用list双链表。
设置一个哈希表保存指向链表的指针，这样既可以查找最快，也可以快速删除。
*/
class Solution{
    private:
        list<pair<int,int> > plist;
        unordered_map<int,list<pair<int,int> >::iterator> umap;
        int capacity;
        void set(int key,int value){
            auto it = umap.find(key);
            if(it!=umap.end()){
                plist.erase(umap[key]);
                plist.push_front({key,value});
                umap[key] = plist.begin();
            }
            else{
                if(capacity==plist.size()){
                    umap.erase(plist.back().first);
                    plist.pop_back();
                }
                plist.push_front({key,value});
                umap[key]=plist.begin();
            }
        }
        int get(int key){
            auto it = umap.find(key);
            if(it!=umap.end()){
                plist.erase(umap[key]);
                plist.push_front({key,it->second->second});
                umap[key]=plist.begin();
                return it->second->second; 
            }
            return -1;
        }
    public:
        vector<int> LRU(vector<vector<int> >& operators, int k) {
               vector<int>  res;
            capacity=k;
            for(int i=0;i<operators.size();i++)
                    operators[i][0]==1?set(operators[i][1],operators[i][2])
                        :res.push_back(get(operators[i][1]));
        return  res;
    }
};