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

LFU缓存中元素的换入换出由两个排序码决定：使用次数cont和时间戳time。定义struct结点并且重写<运算符函数，使用红黑树保存结点，就能实现结点按要求自动排序，另外再使用哈希表保存<key,node>，实现了通过key的查找。然后在get和set的过程中更新cont及time，并且元素装满时进行换出。

struct Node{
    int key;
    int value;
    int cont;
    int time;
    Node(int k,int v,int c,int t):key{k},value{v},cont{c},time{t}{};
    bool operator<(const Node& node) const{
        return cont==node.cont?time<node.time:cont<node.cont;
    }
};

class Solution {
public:
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    int get(int key){
        if(capacity==0) return -1;
        auto iter=hash_map.find(key);
        if(iter!=hash_map.end()){
            Node node=iter->second;
            hash_map.erase(iter);
            lfu_set.erase(node);
            node.cont++;
            node.time=++time;
            hash_map.insert(make_pair(key,node));
            lfu_set.insert(node);
            return node.value;
        }
        else return -1;
    }
    
    void set(int key,int value){
        auto iter=hash_map.find(key);
        if(iter!=hash_map.end()){
            Node node=iter->second;
            hash_map.erase(iter);
            lfu_set.erase(node);
            node.cont++;
            node.time=++time;
            node.value=value;
            hash_map.insert(make_pair(key,node));
            lfu_set.insert(node);
        }
        else{
            if(hash_map.size()>=capacity){
                hash_map.erase(lfu_set.begin()->key);
                lfu_set.erase(lfu_set.begin());
            }
            Node node{key,value,1,++time};
            hash_map.insert(make_pair(key, node));
            lfu_set.insert(node);
        }
    }
    
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        vector<int> result{};
        capacity=k;
        time=0;
        for(auto x:operators){
            if(x[0]==1) set(x[1], x[2]);
            else if(x[0]==2) result.push_back(get(x[1]));
        }
        return result;
    }
private:
    int capacity;
    int time;
    std::set<Node> lfu_set;
    unordered_map<int, Node> hash_map;
};