双hash表，双链表

双hash + 双链表

• hash: <key, list<node>:: iterator></node>

• cnt: <freq, list<node> >
  使用list来模拟双链表</node>

  #include<unordered_map>
  typedef struct node{
    int key, value, freq;
  }node;
  class Solution {
  public:
    int minFreq, hashSize;
    unordered_map<int, list<node>::iterator> hash;
    unordered_map<int, list<node> > cnt;
  
    void set(int x, int y){
        if(hash.find(x) == hash.end()){
            if(hash.size() == hashSize){
                auto t = cnt[minFreq].back();
                hash.erase(t.key);
                cnt[minFreq].pop_back();
                if(cnt[minFreq].size() == 0){
                    cnt.erase(minFreq);
                }
            }
            cnt[1].push_front({x, y, 1});
            hash[x] = cnt[1].begin();
            minFreq = 1;
        }
        else{
            auto t = hash[x];
            int freq = t->freq;
            cnt[freq].erase(t);
            if(cnt[freq].size() == 0){
                cnt.erase(freq);
                if(minFreq == freq) minFreq ++;
            }
            cnt[freq + 1].push_front({x, y, freq + 1});
            hash[x] = cnt[freq + 1].begin();
        }
    }
  
    int get(int x){
        if(hash.find(x) == hash.end()) return -1;
        auto t = hash[x];
        int freq = t->freq;
        int y = t->value;
        cnt[freq].erase(t);
        if(cnt[freq].size() == 0){
            cnt.erase(freq);
            if(minFreq == freq) minFreq++;
        }
        cnt[freq + 1].push_front({x, y, freq + 1});
        hash[x] = cnt[freq + 1].begin();
        return y;
    }
  
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> ans;
        if(k <= 0) return ans;
        minFreq = 0, hashSize = k;
        for(int i = 0; i < operators.size(); i++){
            auto t = operators[i];
            if(t[0] == 1){
                set(t[1], t[2]);
            }
            else{
                ans.push_back(get(t[1]));
            }
        }
        return ans;
    }
  };