LRU&LFU实现方式C++

参考文章

1、LRU

https://leetcode.cn/problems/lru-cache/

typedef pair<int, int> PII;
class LRUCache {
public:
    int cap, cnt;
    //pair<第几个插入的，val>
    int l[200010], r[200010], h[200010], idx; //h用来通过key快速找到结点
    PII e[200010]; 
    //维护当前最后一个节点是第几个插入的

    void insert(int k, PII x){
        e[idx] = x;
        l[idx] = k;
        r[idx] = r[k];
        l[r[k]] = idx;
        r[k] = idx++;
        cnt++;
    }

    void remove(int k){
        r[l[k]] = r[k];
        l[r[k]] = l[k];
        cnt--;
    }

    LRUCache(int capacity) {
        this->cap = capacity;
        memset(l, -1, sizeof l);
        memset(r, -1, sizeof r);
        memset(h, -1, sizeof h);
        r[0] = 1, l[1] = 0;  //0,1是哨兵
        idx = 2;
        cnt = 0;
    }
    
    //用头插法维护这个双链表！
    int get(int key) {
        if(h[key] == -1) return -1;
        //把链表中老的点删除
        PII t = e[h[key]];
        remove(h[key]);
        h[key] = idx;
        insert(0, t);  //会更新idx
        return t.second;
    }
    
    void put(int key, int value) {
        if(h[key] != -1) remove(h[key]); 
        insert(0, {key, value});
        h[key] = idx - 1;  //更新h[key]
        if(cnt > cap){  //需要逐出
            //删除h中
            h[e[l[1]].first] = -1;
            remove(l[1]);
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

2、LFU

https://leetcode.cn/problems/lfu-cache/description/

//参考思路  https://leetcode.cn/problems/lfu-cache/solutions/977393/lru-lfu-by-mats9693-sy1x/

const int N = 200010;
class LFUCache {
public:
    struct Node{
        int key, value, freq;
    };

    int h[N], mp[N], l[N], r[N], idx, cap, n;  //mp[]:用key索引idx
    int ct[N];   //freq对应的结点的个数
    Node e[N];  //e[]:用idx索引，
    int pu;

    LFUCache(int capacity) {
        this->cap = capacity;
        memset(h, -1, sizeof h);
        memset(l, -1, sizeof l);
        memset(r, -1, sizeof r);
        memset(mp, -1, sizeof mp);
        r[0] = 1, l[1] = 0, idx = 2;
        pu = 0;
        n = 0;
    }

    void insert(int k, Node x){
        e[idx] = x;
        r[idx] = r[k];
        l[idx] = k;
        r[k] = idx;
        l[r[idx]] = idx;
        idx++;
        n++;
    }

    void remove(int k){
        r[l[k]] = r[k];
        l[r[k]] = l[k];
        n--;
    }
    
    int get(int key) {
        if(mp[key] == -1) return -1;  
        auto t = e[mp[key]]; 
        //如何知道当前结点右边的idx
        int rr = r[mp[key]];
        bool flag = false;
        if(ct[t.freq + 1] > 0){  //插入到freq+1部分的最前面
            //先删除掉freq的这个结点
            remove(mp[key]);
            int pos = h[t.freq + 1];
            insert(l[pos], {t.key, t.value, t.freq + 1});  
            // insert(l[pos], {t.key, t.value, t.freq});
            flag = true;
        }
        //没有freq+1的部分，但是有freq部分（不止自己一个），那么插入到freq部分的最前面
        else if(ct[t.freq] > 1 && e[h[t.freq]].key != t.key){ 
            remove(mp[key]);
            int pos = h[t.freq];
            insert(l[pos], {t.key, t.value, t.freq + 1});  
            // insert(l[pos], {t.key, t.value, t.freq});  
            flag = true;
        }
        //更新h
        if(flag) h[t.freq + 1] = idx - 1, mp[key] = idx - 1;  //因为更换了位置，所以mp也要更改
        else {
            h[t.freq + 1] = mp[key] = h[t.freq];
            e[mp[key]].freq++;   //这种情况也要++
        }

        if(ct[t.freq] <= 1){  //没有其他freq = n的结点
            h[t.freq] = -1;    //注意：这里key是不会消失的，只是ct变化了而已
        } 
        else if(e[h[t.freq]].key == t.key){  //如果ct > 1且它原先是作为头部存在的
            //错误想法:
            // h[t.freq] = r[idx - 1];
            // h[t.freq] = r[h[t.freq + 1]];  
            //**正确想法**: 要用它原先的右边!
            h[t.freq] = rr;
        }
        ct[t.freq]--;
        ct[t.freq + 1]++;
        pu = mp[key];
        // e[pu].freq++;     //将缓存次数+1
        return t.value;
    }   
    
    void put(int key, int value) {
        if(mp[key] != -1) {
            get(key);
            //map[key]可能已经更改了,所以下面注释代码是错误的
            // e[mp[key]].value = value;
            e[pu].value = value;
            return;
        }
        //key不存在
        if(n >= cap){ //逐出最后一个结点
            auto t = e[l[1]];
            remove(l[1]);
            mp[t.key] = -1;  //一定要把key清掉
            if(--ct[t.freq] <= 0) h[t.freq] = -1;//如果由于逐出key导致ct->0，那么mp也要清除
        }
        //插入,此时freq = 1
        if(ct[1] > 0){  //需要移动到freq=1部分的开头
            int pos = h[1];    
            insert(l[pos], {key, value, 1});
        }
        else{  //插入到末尾
            insert(l[1], {key, value, 1});
        }
        h[1] = idx - 1;
        ct[1]++;
        mp[key] = idx - 1;
    }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */