原文链接： LRU和LFU实现 - Dillonh

LRU

原题链接： LeetCode146. LRU 缓存机制

class LRUCache {
public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        if(mp.find(key) == mp.end()) return -1;
        put(key, mp[key]->second);//借助put函数来进行更新
        return mp[key]->second;
    }

    void put(int key, int value) {
        if(mp.find(key) != mp.end()) {
            recent.erase(mp[key]);
        } else if(mp.size() == capacity) {
                mp.erase(recent.back().first);
                recent.pop_back();
        }
        recent.push_front(make_pair(key, value));
        mp[key] = recent.begin();
    }
private:
    int capacity;//LRU的容量
    list<pair<int,int>> recent;//用双向链表来实现LRU的功能，头为最近使用，尾为最远使用
    unordered_map<int, list<pair<int,int>>::iterator> mp;//key值对应队列中的结点
};

LFU

原题链接： LeetCode460. LFU 缓存

class LFUCache {
public:
    LFUCache(int capacity) : capacity(capacity), lst(0) {}

    int get(int key) {
        if(all.count(key) == 0) return -1;
        put(key, all[key].first);//借助put函数来更新
        return all[key].first;
    }

    void put(int key, int value) {
        if(capacity == 0) return;
        if(all.count(key) == 0) {
            if((int)all.size() >= capacity) {
                all.erase(fre[lst].back());
                pos.erase(fre[lst].back());
                fre[lst].pop_back();
            }
            lst = 1;//新增加一个key那么最低频率肯定是1
            all[key] = {value, 1};
            fre[1].push_front(key);
            pos[key] = fre[1].begin();
        } else {
            int cnt = all[key].second;
            ++all[key].second;
            fre[cnt].erase(pos[key]);
            fre[cnt+1].push_front(key);
            pos[key] = fre[cnt+1].begin();
            all[key].first = value;
            if(fre[lst].size() == 0) ++lst;
        }
    }
private:
    int capacity, lst;//LFU的容量、最低频率
    unordered_map<int, list<int>> fre;//每个频率存一个链表
    unordered_map<int, pair<int,int>> all;//key对应的value和频率
    unordered_map<int, list<int>::iterator> pos;//key对应的链表中的位置
};