Leetcode 460: LFU Cache

https://leetcode.com/problems/lfu-cache/description/

---

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Note:

This question is a follow-up to Leetcode 146: LRU

The key points are:

(1): We need to get() a element in O(1), so hash map is a choice;

(2): We need to memorize both frequency and order of the elements, which are not covered by a hash map. So we need add some other kind of data structure. Since we need to erase a element in O(1) too, so list should be a choice;

(3): Using a list, it is true that we can erase one element in O(1), but we need to localize the position of the element in O(1) too. So another hash map is needed to correlate the key and the position in the list;

(4): We also need to record the frequency of each element;

(5): We need to maintain the least frequency as well.

See the code below:

class LFUCache {
public:
    LFUCache(int capacity) {
        cap = capacity;
        minF = 0;
    }

    int get(int key) {
        if(!ump.count(key)) return -1;
        freq[ump[key].second].erase(itr[key]);
        ++ump[key].second;
        freq[ump[key].second].push_back(key);
        itr[key] = --freq[ump[key].second].end();//cannot use rbegin() here; 
                                                                     //different iterator types
        if(freq[minF].empty()) ++minF;
        return ump[key].first;
    }

    void put(int key, int value) {
        if(cap<=0) return;
        if(get(key) != -1) { //must use get() here, to update the freq and minF; 
                                                 //otherwise, we have to update them individually.
            ump[key].first = value;
            return;
        }
        if(ump.size() >= cap) {
            ump.erase(freq[minF].front());//smallest freq and least used;
            itr.erase(freq[minF].front());
            freq[minF].pop_front();
        }
        ump[key] = {value, 1};
        freq[1].push_back(key);
        itr[key] = --freq[1].end();
        minF = 1;
    }

private:
    int cap, minF;
    unordered_map<int, pair<int, int>> ump; //<key, <value, frequency>>
    unordered_map<int, list<int>::iterator> itr; //<key, <iterator of key> in the list>
    unordered_map<int, list<int>> freq; //<freq, <key>>
};

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