LFU算法

#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;
class LFUCache {
public:
    LFUCache(int capacity) {
    	_capacity = capacity;
        _min_frequent = 1;
    }
    struct CacheNode
    {
    	int key;
    	int value;
    	int frequent;
    };
    //此函數剛開始沒有抽象出來。因為沒有了解LFU寫入還有修改資料
    int& touch(list<CacheNode>::iterator itr){
       	CacheNode& node = *itr;
       	int old_frequent = node.frequent;
       	int new_frequent = ++node.frequent;
       	_cache[new_frequent].splice(_cache[new_frequent].begin(), _cache[old_frequent], itr);
       	//splice厲害 抵三句 _cache[frequent].push_front(node); _cache[frequent - 1].erase(itr); _map[itr->key] = _cache[new_frequent].begin();
       	if (_cache[old_frequent].size() == 0 && _min_frequent == old_frequent){
       		_min_frequent = new_frequent;
       	}
       	return itr->value;//begin傳回iterator 與之對應的front()
    }
    int get(int key) {
    	auto itr = _map.find(key);//測試後發現find快于count,itr對應的是pair
        if (itr == _map.end()) {
        	return -1;
        }
       	return touch(itr->second);
    }
    void put(int key, int value) {
        if (_capacity == 0){
        	return;
        }
        //1.查詢是否存在，存在更新資料
        auto itr = _map.find(key);
        if (itr != _map.end()){
        	touch(itr->second) = value;
        }else{
        	//2.删除多餘節點，更新_min_frequent
        	if (_map.size() >= _capacity) {
        	    //cout <<"_min_frequent" <<_min_frequent <<endl;
	        	int key = _cache[_min_frequent].back().key;
				//cout <<"delete:" << _cache[_min_frequent].back().value << " frequent:" << _cache[_min_frequent].back().frequent << endl;
	        	_map.erase(key);
	        	_cache[_min_frequent].pop_back();
	        	if (_cache[_min_frequent].size() == 0 && _map.size() > 0){
	        		while (_cache[++_min_frequent].size() == 0);
	        	}
        	}
            //插入節點
        	CacheNode node{key, value, 1};
        	_cache[1].push_front(node);
        	_map[key] = _cache[1].begin();
        	_min_frequent = 1;
        }
    }
    size_t _capacity;
    int _min_frequent;
    unordered_map<int, list<CacheNode> > _cache;
    unordered_map<int, list<CacheNode>::iterator> _map;
};
int main() {
	LFUCache cache = *((LFUCache *) new LFUCache(3));
	cache.put(2, 2);
	cache.put(1, 1);
	cout << cache.get(2) <<endl;    
	cout << cache.get(1) <<endl;
	cout << cache.get(2) <<endl;  
	cache.put(3, 3);   
	cache.put(4, 4);  
	cout << cache.get(3) <<endl; 
	cout << cache.get(2) <<endl;
	cout << cache.get(1) <<endl;
	cout << cache.get(4) <<endl;
	return 0;
}