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

class Solution {
private:
    list<pair<int, int>> lst;
    unordered_map<int, pair<int, int>>mp;//建立key对结构的索引
public:
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        vector<int> ret;
        for(auto &val : operators)
        {
            if(val[0] == 1)
            {
                pair<int, int>temp;
                temp.first = val[1];
                temp.second = val[2];
                if(lst.size()<k)//当页面未满，直接插入即可，并建立索引
                {
                     lst.push_front(temp);
                     mp[val[1]] = temp;
                }
                else//当页面已满却想要插入时，删除list尾部结点，在头部加入新节点
                {
                     mp[lst.back().first].first = 0;//将废弃页面的key置0
                     mp[val[1]] = temp;//为新页面建立索引
                     lst.pop_back();
                     lst.push_front(temp);
                }
            }
            else if(val[0] == 2)
            {             
                pair<int, int> tpir =  mp[val[1]];
                if(tpir.first == 0)//key为零说明list中无此页面
                    ret.emplace_back(-1);
                else
                {
                    int res = mp[val[1]].second;
                    ret.emplace_back(res);
                    lst.remove(tpir);//删除查询的页面，并将其移动到最前方
                    lst.push_front(tpir);
                }
            }
        }
        return ret;
        // write code here
    }
};