LFU Cache - Implement put and get functions in O(1) time, removing the least frequently used data when the capacity is full.

lfucache.cpp

#include "lfucache.hpp"

int main() {
	LFUCache obj(2);
	obj.put(2,2);
	cout << obj.get(1) << endl;
	obj.put(3,3);
	cout << obj.get(2) << endl;
	cout << obj.get(3) << endl;
	obj.put(4,4);
	cout << obj.get(1) << endl;
	cout << obj.get(3) << endl;
	cout << obj.get(4) << endl;
	cout << obj.get(2) << endl;
}

lfucache.hpp

#include <iostream>
#include <list>
#include <unordered_map>
#include <utility>

using namespace std;

class LFUCache {
private:
    using int_itr = pair<int, list<pair<int,int>>::iterator>;
    using list_pair = list<pair<int, int>>;
    unordered_map<int, int_itr> itr_table_;
    unordered_map<int, list_pair> freq_table_;
    int size_{0};
    int min_freq_;
    const int CAPACITY_;
public:
    LFUCache(int capacity): CAPACITY_{capacity} { }
    
    int get(int key) {
        // return -1 if the key can't be found
        if (!itr_table_.count(key)) {
            return -1;
        }
        // retrieve the iterator and the value to return
        auto itr = itr_table_[key].second;
        auto val = itr->second;
        
        // erase the itr from the list, which is O(1) since this is a doubly linked list.
        // increment the first value in the pair by one to update it's frequency.
        freq_table_[itr_table_[key].first++].erase(itr);
        
        // if there are no more elements that have been used the min_freq amount of times, erase that table and increment min_freq
        // to reflect that.
        if (freq_table_[min_freq_].size() == 0) {
            freq_table_.erase(min_freq_);
            ++min_freq_;
        }
        
        // add the value to the end of the list that represents how much it has been used. This is because it is the most
        // recently used value and should be the last value erased in the list in the case of a tie.
        freq_table_[itr_table_[key].first].push_back({key, val});
        
        // update the key's iterator to reflect it's new spot. O(1) time due to doubly linked list.
        itr_table_[key].second = --freq_table_[itr_table_[key].first].end();
        return val;
    }
    
    void put(int key, int value) {
        // error checking for if this lfucache is always empty
        if (CAPACITY_ == 0){
            return;        
        } 
        
        // if you find the key, then you should simply update it's frequency (which is done in the get function)
        // and update it's value with the new value.
        int found = get(key);
        if (found != -1) {
            itr_table_[key].second->second = value;
            return;
        }
        
        // if the size reaches the CAPACITY, erase the front of the list that represents
        // the min_freq, since that is the least recently used and least frequently used element.
        // reflect this in both the itr_table and the freq_table. 
        if (size_ == CAPACITY_) {
            itr_table_.erase(freq_table_[min_freq_].front().first);
            freq_table_[min_freq_].pop_front();
            --size_;
        }
        // push the key and value to the first spot, since it has only been used once.
        // update the itr_table to grab the itr at the end of the list, since the number inserted
        // is the most recently used number. Set min_freq_ to 1 in case the min_freq is different.
        freq_table_[1].push_back({key, value});
        itr_table_[key] = {1, --freq_table_[1].end()};
        ++size_;
        min_freq_ = 1;
    }
};

I solved this question recently following the requirements on leetcode. The question is posted below.
This is made public for an application I am filling out, so they can see some of my code, without the code itself being too cumbersome.

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