LFU Cache (Leetcode 460)

LFU

LFU Cache 的基本做法应该是存一个frequency list (doubly linked list), 这个List的每个node存frequency value，和一个sublist表示都有哪些值属于这个list. 另外再建一个hashmap，存key和list里面的位置.

在这里，我们用三个hash table，来完成以上的工作.
参考了这篇文章，非常巧妙，而且简洁
http://www.cnblogs.com/grandyang/p/6258459.html

class LFUCache {
public:
    LFUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        if(mp.count(key) == 0) return -1;
        frequency[mp[key].second].erase(storage[key]);
        mp[key].second++;
        frequency[mp[key].second].push_back(key);
        storage[key] = --frequency[mp[key].second].end();
        if(frequency[minFreq].size() == 0) minFreq++;
        return mp[key].first;
    }
    
    void put(int key, int value) {
        if(cap <= 0) return;
        if(get(key) != -1){
            mp[key].first = value;
            return;
        }
        if(mp.size() >= cap){
            mp.erase(frequency[minFreq].front());
            storage.erase(frequency[minFreq].front());
            frequency[minFreq].pop_front();
        }
        mp[key] = {value, 1};
        frequency[1].push_back(key);
        storage[key] = --frequency[1].end();
        minFreq = 1;
    }
private:
    int cap, minFreq = 0;
    unordered_map<int, pair<int, int>> mp;
    unordered_map<int, list<int>> frequency;
    unordered_map<int, list<int>::iterator> storage;
};

/**
 * 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);
 */