相关问题：146. LRU Cache
问题：
设计类LFUCache，实现LFU Cache
Least Frequently Used
优先度为：访问频率最多优先 的缓存。
- 缓存大小一定，capacity
- get(key)：通过key查找value，若缓存中不存在key，返回-1
- put(key, value)：插入缓存key=value。
Example 1:
Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
Explanation
// cnt(x) = the use counter for key x
// cache=[] will show the last used order for tiebreakers (leftmost element is most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1); // cache=[1,_], cnt(1)=1
lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1); // return 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3); // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
// cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4); // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
// cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4); // return 4
// cache=[3,4], cnt(4)=2, cnt(3)=3
Constraints:
0 <= capacity, key, value <= 10^4
At most 10^5 calls will be made to get and put.
解法：LFU
c++中 利用 map 和 unordered_map 来实现：
- cache：map：存储cache链表(头新，尾旧)。<frequency: list>（拥有frequency优先级排序）
- ?? 注意：list若==empty，记得要删除map中这个frequency元素。
- kl：unordered_map：存储对应key在cache中的位置<frequency, list_idx>，方便直接访问。
- kv：另：为了存储value，追加unordered_map保存key：value对应关系。
那么，对于cache，我们有以下两个基本操作：
- 追加key：value对
- update(key, value)【假设，此操作cache已经不超过最大容量】
- 若key存在于cache中
- 在list中找到key（定位：kl[key]），将key从cache中删除：freq=kl[key].first; list=cache[kl[key].first]
- cache[kl[key].first].erase(kl[key].second)
- 解释：->cache[kl[key].freq].erase(kl[key].list_idx)
- ?? 若此时list==null，cache.erase(freq)
- 1. freq++
- 2. 重新加到list头：list.push_front(key)，更新key在list中的位置：kl[key]={freq, list.begin()}
- 3. 更新 kv[key]=value
- 在list中找到key（定位：kl[key]），将key从cache中删除：freq=kl[key].first; list=cache[kl[key].first]
- 若key不存在于cache中：freq=0, list=cache[freq+1]
- 1. freq++
- 2. 将key加到list头：list.push_front(key)，更新key在list中的位置：kl[key]={freq, list.begin()}
- 3. 更新 kv[key]=value
- 若key存在于cache中
- update(key, value)【假设，此操作cache已经不超过最大容量】
- 删除最老的元素（当size超出cache容量）
- outlast()：last = list.back() (list = cache.begin().second)
- kl.erase(last)
- kv.erase(last)
- list.pop_back()
- ?? 若此时list==null，cache.erase(freq)
再看题目所求：
- get(key)：
- update(key)
- return kv[key]
- put(key, value)
- 若cache==最大容量：删除最老元素：outlast()
- 此时，cache一定不超过最大容量：再进行：update(key, value)
- ?? 注意：若outlast失败，那证明现在的cache==最大容量，依然不能update。
代码参考：
1 class LFUCache { 2 public: 3 LFUCache(int capacity) { 4 size = capacity; 5 } 6 7 int get(int key) { 8 //cout<<"get:"<<key<<endl; 9 if(kv.count(key)) { 10 update(key, kv[key]); 11 return kv[key]; 12 } 13 return -1; 14 } 15 16 void put(int key, int value) { 17 //cout<<"put:"<<key<<"= "<<value<<endl; 18 if(!kv.count(key) && kv.size()==size) { 19 //cout<<"outlast"<<endl; 20 if(false==outlast()) return; 21 } 22 update(key, value); 23 return; 24 } 25 private: 26 int size; 27 map<int, list<int>> cache;//frequency: key list(oldest->back; new->begin) 28 unordered_map<int, int> kv;//key:value 29 unordered_map<int, pair<int, list<int>::iterator>> kf;//key:frequency,idx 30 void update(int key, int value) { 31 if(kv.count(key)) {//exist 32 cache[kf[key].first].erase(kf[key].second); 33 if(cache[kf[key].first].empty()) cache.erase(kf[key].first); 34 } 35 kv[key] = value; 36 kf[key].first++; 37 cache[kf[key].first].push_front(key); 38 kf[key].second = cache[kf[key].first].begin(); 39 } 40 bool outlast() { 41 if(cache.empty()) return false; 42 int last = cache.begin()->second.back();//cache.begin->minimal frequency 43 //cout<<"out:"<<last<<endl; 44 cache.begin()->second.pop_back(); 45 if(cache.begin()->second.empty()) cache.erase(cache.begin()); 46 kv.erase(last); 47 kf.erase(last); 48 return true; 49 } 50 }; 51 52 /** 53 * Your LFUCache object will be instantiated and called as such: 54 * LFUCache* obj = new LFUCache(capacity); 55 * int param_1 = obj->get(key); 56 * obj->put(key,value); 57 */