# O(1) multimap+unordered_map solution

• This is an implementation of the O(1) algorithm introduced in http://www.deepakvadgama.com/blog/lfu-cache-in-O(1)/.
Use the frequency as the multimap's key and {key,value} as the multimap's value. The insertion order is preserved in the multimap, so the first entry in the multimap is always the least frequently used and least used entry.
To facilitate O(1) deletion, we need an unordered_map to help locate the entry in the multimap by its key value. If the size limit is reached, we delete first and then insert. Doing it backwards will result in the deletion of the newly added entry.
Since both get() and put() is regarded as one visit, we update the frequency in get() and invoke get() in put().When updating the frequency, just move(i.e. delete and insert) the entry to key+1 level in the multimap.

``````class LFUCache{
multimap<int,pair<int,int>> dict;
unordered_map<int,multimap<int,pair<int,int>>::iterator> table;
int size_limit;
public:
// @param capacity, an integer
LFUCache(int capacity) {
size_limit = capacity;
}

// @param key, an integer
// @param value, an integer
// @return nothing
void put(int key, int value) {
if( size_limit==0 ) return;
if( get(key)==-1 ){
if( table.size()>=size_limit ){
int k = (dict.begin()->second).first;
dict.erase(dict.begin());
table.erase(k);
}
multimap<int,pair<int,int>>::iterator it = dict.insert({1,{key,value}});
table[key] = it;
}
else table[key]->second = {key,value};
}

// @return an integer
int get(int key) {