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

class Solution {
public:
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    struct record{
        int key;
        int value;
        int accessTime;
        record(int x,int y):key(x),value(y),accessTime(1){}
    };

    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        listSize = 0;
        vector<int> res;
        if(operators.empty() || k < 1)
            return res;
        for(const auto& x : operators){
            if(x[0] < 2)
                set(x[1],x[2],k);
            else
                res.emplace_back(get(x[1]));
        }
        return res;
    }

    void set(int key,int value,const int& k){
        if(um1.find(key) != um1.end()){
            um1[key]->value = value;
            get(key);
            return;
        }
        
        if(listSize < k){
            if(um2.find(1) != um2.end()){
                list<record>& ll = *um2[1];
                ll.emplace_front(record(key,value));
                um1.emplace(make_pair(key,ll.begin()));
            }else{
                list<record> ll{record(key,value)};
                ls.emplace_front(ll);
                ll = ls.front();
                um2.emplace(make_pair(1,ls.begin()));
                um1.emplace(make_pair(key,um2[1]->begin()));
            }
            ++listSize;
        }else{
            auto i = ls.begin();
            while(i->size() < 1)
                ++i;
            um1.erase(i->back().key);
            i->pop_back();
            i = ls.begin();
            i->emplace_front(record(key,value));
            um1.emplace(key,i->begin());
        }
    }

    int get(int key){
        if(um1.find(key) != um1.end()){
            int time = ++um1[key]->accessTime;
            list<record>& l1 = *um2[time - 1];
            if(um2.find(time) != um2.end()){
                list<record>& l2 = *um2[time];
                l2.emplace_front(*um1[key]);
                l1.erase(um1[key]);
                um1[key] = l2.begin();
            }else{
                list<record> newls;
                newls.emplace_front(*um1[key]);
                l1.erase(um1[key]);
                auto i = um2[time-1];
                ++i;
                i = ls.emplace(i,newls);
                um2.emplace(make_pair(time,i));
                um1[key] = um2[time]->begin();
            }
            return um1[key]->value;
        }
        return -1;
    }
    int listSize = 0;
private:
    list<list<record>> ls;
    unordered_map<int,list<record>::iterator> um1;
    unordered_map<int,list<list<record>>::iterator> um2;
};