LFU Cache

#include<iostream>
#include<map>
#include<list>
#include<vector>

using namespace std;

class LFUCache {

    int size;  // Size of LFU cache
    int count; // keys track of the elements that are pushed.

    map <int, pair<int, int>> cache; // LFU cache table stores < key, < value, frequency > >

    // Table stores list of keys based on their frequency. The first element of the list is the LRU key.
    map <int, list<int>> freq_table;

    public:

    LFUCache (int arg_size) : size (arg_size), count(0) { }

    // Update the frequency of the key
    void Update_FrequencyTable (int freq, int key) {

        // Update would involve deleting the previous pair <frequency, <key>> from the list.
        if (freq > 1) { // Element should be already be present at previous frequency. So remove it.
            freq_table[freq-1].remove(key);
        }
        freq_table[freq].push_back(key);

        cout << "Frequency Table" << endl;
        cout << "===============" << endl;
        for (int freq=1; freq<=count; freq++) {
             cout << "Freq [" << freq << "] : ";
             list<int> :: iterator it;
             for (it = freq_table[freq].begin(); it != freq_table[freq].end(); ++it)
                  cout << *it << " ";
             cout << endl;
        }
    }

    int Get (int key) {
        cout << "\nOperation GET : " << key << endl;
        if (cache.find(key) != cache.end()) {
            cache[key].second += 1;
            int freq = cache[key].second;
            Update_FrequencyTable (freq, key);
            cout << "Return ----> ";
            return cache[key].first;
        }
        return -1;
    }

    void Put (int key, int value) {

        if (size == 0)
            return;

        cout << "\nOperation PUT : [" << key << ":" << value << "]" << endl;

        if (cache.find(key) != cache.end()) { // Key is found in the cache
            cache[key].first = value;
            cache[key].second += 1;
            int freq = cache[key].second;
            Update_FrequencyTable (freq, key);
        } else { // Key not found in the cache
            count++;
            if (cache.size() == size) { // Cache is already full
                cout  << "Cache is full !!" << endl;
                for (int freq=1; freq<=count; freq++) {
                    if (freq_table.find(freq) != freq_table.end() and freq_table[freq].size() > 0) {
                        int key = freq_table[freq].front();
                        cout << "Erasing key : " << key << endl;
                        cache.erase(key);
                        freq_table[freq].pop_front();
                        break;
                    }
                }
            }
            cache[key].first = value;
            cache[key].second = 1;
            Update_FrequencyTable (1, key);
        }
    }
};

int main() {

    LFUCache cache(2);

    cache.Put(1,1);
    cache.Put(2,2);
    cout << cache.Get(1) << endl;
    cache.Put(3,3);
    cout << cache.Get(2) << endl;
    cout << cache.Get(3) << endl;
    cache.Put(4,4);
    cout << cache.Get(1) << endl;
    cout << cache.Get(3) << endl;
    cout << cache.Get(4) << endl;
    return 0;
}

Operation PUT : [1:1]
Frequency Table
===============
Freq [1] : 1 

Operation PUT : [2:2]
Frequency Table
===============
Freq [1] : 1 2 
Freq [2] : 

Operation GET : 1
Frequency Table
===============
Freq [1] : 2 
Freq [2] : 1 
Return ----> 1

Operation PUT : [3:3]
Cache is full !!
Erasing key : 2
Frequency Table
===============
Freq [1] : 3 
Freq [2] : 1 
Freq [3] : 

Operation GET : 2
-1

Operation GET : 3
Frequency Table
===============
Freq [1] : 
Freq [2] : 1 3 
Freq [3] : 
Return ----> 3

Operation PUT : [4:4]
Cache is full !!
Erasing key : 1
Frequency Table
===============
Freq [1] : 4 
Freq [2] : 3 
Freq [3] : 
Freq [4] : 

Operation GET : 1
-1

Operation GET : 3
Frequency Table
===============
Freq [1] : 4 
Freq [2] : 
Freq [3] : 3 
Freq [4] : 
Return ----> 3

Operation GET : 4
Frequency Table
===============
Freq [1] : 
Freq [2] : 4 
Freq [3] : 3 
Freq [4] : 
Return ----> 4