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