LFU Cache

Similar to LRU http://techinpad.blogspot.com/2015/06/leetcode-lru-cache.html, implement a LFU, which is the least frequently used cache.

Analysis: multimap should be the best data structure to use.

class LFUCache{
    unordered_map<int, multimap<int, pair<int,int>>::iterator> mMap;
    multimap<int, pair<int,int>> mList;
    int mCap;
public:
    LFUCache(int capacity) {
        mCap = capacity;
    }
    
    void moveToHead(int key) {
        multimap<int, pair<int,int>>::iterator it = mMap[key];
        pair<int, pair<int,int>> n(it->first+1, pair<int,int>(it->second.first, it->second.second));
        mList.erase(it);
        mMap[key] = mList.insert(n);
    }
    
    int get(int key) {
        if(!mMap.count(key)) return -1;
        moveToHead(key);
        return mMap[key]->second.second;
    }
    
    void set(int key, int value) {
        
        if(mMap.count(key)) {
            mMap[key]->second.second = value;
            moveToHead(key);
            return;
        } 
        
        if(mList.size() == mCap) {
            auto it = mList.begin();
            mMap.erase(it->second.first);
            mList.erase(it);
        }
        pair<int,pair<int,int>> n(1, pair<int,int>(key, value));
        mMap[key] = mList.insert(n);
        
    }
};