# LRU/LFU Cache 設計
- [146. LRU Cache](https://leetcode.com/problems/lru-cache/)
- 維護最近用過的 list: `3<-8<-5<-6`
- Insert(6) : `6<-3<-8<-5`
- Insert(4) : `4<-6<-3<-8`

    class LRUCache {
        int CAP;
        list<int> l;
        unordered_map<int, pair<list<int>::iterator, int>> mp;
    public:
        LRUCache(int capacity) {
            ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
            CAP = capacity;
        }

        int get(int key) {
            if(mp.count(key)==0)    return -1;

            l.push_front(key);
            l.erase(mp[key].first);   
            mp[key].first = l.begin();
            return mp[key].second;
        }

        void put(int key, int value) {
            if(get(key)!=-1){
                mp[key].second = value;
            }else{
                if(l.size() == CAP){
                    mp.erase(l.back());
                    l.pop_back();
                }
                l.push_front(key);
                mp[key] = {l.begin(), value};
            }
        }
    };

- [460. LFU Cache](https://leetcode.com/problems/lfu-cache/submissions/)
- 維護每個頻率的 list: `1: 3<-8`, `2:5<-6`
- Insert(4) : `1: 8<-4`, `2:5<-6`
- Insert(8) : `1: 4`, `2:5<-6<-8`
- 需要 2 個 map
- frequency -> list
- key -> (value, frequency, list position)

    struct node{
        int value, freq;
        list<int>::iterator it;
    };


    class LFUCache {    
        int CAP, minF;
        unordered_map<int, node> mp;
        unordered_map<int, list<int>> data;
    public:
        LFUCache(int capacity) {
            ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
            CAP = capacity;
            minF = 1;
        }

        int get(int key) {
            if(mp.count(key)==0)    return -1;

            data[mp[key].freq].erase(mp[key].it);
            mp[key].freq++;
            data[mp[key].freq].push_back(key);
            mp[key].it = prev( data[mp[key].freq].end());
            if(data[minF].size()==0)    minF++;
            return mp[key].value;
        }

        void put(int key, int value) {
            if(CAP==0)  return;

            if(get(key)!=-1){
                mp[key].value = value;
            }else{
                if(mp.size() == CAP){
                    mp.erase(data[minF].front());
                    data[minF].pop_front();
                }
                data[1].push_back(key);
                mp[key] = {value, 1, prev(data[1].end())};
                minF = 1;
            }
        }
    };