LRU

LRU

核心思想：优先淘汰最不被使用的元素，保留最经常被访问的k个元素，使得o(1)时间内高效完成对数据的查询操作，又兼顾了空间问题

• “最近使用”意味着一个数据被读取或者写入后，其“使用时间”被更新到当前时间点。

• “最少使用”即最长时间未被访问，则是最“冷”的数据，应被淘汰。

常用于操作系统页面置换，数据库缓存，web缓存等场景

#include<bits/stdc++.h>

using namespace std;

class LRU {
public:
    LRU() {}
    LRU(int capacity_) : capacity(capacity_) {}

    int get(int key) {
        auto it = mp.find(key);
        if (it != mp.end()) {
            cache.splice(cache.begin(), cache, it->second); // cache中查找查到的元素并移动到链表首部
        }
        else {
            return -1;
        }
    }

    void set(int key, int value) {
        auto it = mp.find(key);
        if (it == mp.end()) {
            if (cache.size() == capacity) {
                auto del = cache.back();
                mp.erase(del.first);
                cache.pop_back();
            }
            cache.emplace_front(key, value);
            mp[key] = cache.begin();
        }
        else {
            it->second->second = value;
            cache.splice(cache.begin(), cache, it->second);
        }
    }
private:
    int capacity;
    list<pair<int, int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> mp;
};

---

LFU

是LRU的适用范围更大版本，LRU可以看作是频率为1的LFU

LFU 的核心思想是：当缓存空间满时，优先淘汰访问频率最低的数据。

• 每次对某个 key 的 get 或 put 操作，都会使该 key 的访问“频率”加 1。

• 淘汰时，选取访问频率最小的那个 key；若有多个频率相同，则通常再根据“最久未被使用”原则（即在该频率列表中淘汰最旧的节点）。

LFU 适合“热点”比较明显且长期稳定的场景，比如某些数据库缓存或网页缓存。

#include<bits/stdc++.h>

using namespace std;

class LFU {
public:
    int get(int key) {
        if (!cache.count(key)) return -1;
        auto [val, cnt, lst] = cache[key];

        cntlist[cnt].erase(lst);
        if (cntlist.empty() && cnt == mincnt) {
            cache.erase(cnt);
            mincnt++;
        }

        cnt++;
        cntlist[cnt].push_front(key);
        cache[key] = { val, cnt, cntlist[cnt].begin() };
        return val;
    }

    void put(int key, int value) {
        if (cap == 0) return;
        if (cache.contains(key)) {
            cache[key].value = value;
            get(key);
            return;
        }

        if (siz == cap) {
            int minuse = cntlist[mincnt].back();
            cntlist[mincnt].pop_back();
            cache.erase(minuse);
            siz--;
        }
        
        cntlist[1].push_front(key);
        cache[key] = { value, 1, cntlist[1].begin() };
        mincnt = 1;
        siz++;
    }
private:
    struct node {
        int value;
        int cnt;
        list<int>::iterator it;
    };
    int cap, siz, mincnt;
    unordered_map<int, node> cache;
    unordered_map<int, list<int>> cntlist;
};