Leetcode 460 Solution

class LFUCache {
    unordered_map<int, tuple<int, int, list<int>::iterator>> m;
    map<int, list<int>> freqs;

    int m_cap;
public:
    list<int>::iterator insertFreq(int freq, int key) {
        freqs[freq].push_back(key);
        return --freqs[freq].end();
    }

    void eraseFreq(int freq, const list<int>::iterator& it) {
        freqs[freq].erase(it);
        if (freqs[freq].empty())
            freqs.erase(freq);
    }

    LFUCache(int capacity) {
        m_cap = capacity;
    }

    int get(int key) {
        auto it = m.find(key);

        if (it == m.end())
            return -1;

        int& val = std::get<0>(it->second);
        int& freq = std::get<1>(it->second);
        auto& list_it = std::get<2>(it->second);

        eraseFreq(freq, list_it);

        freq += 1;

        list_it = insertFreq(freq, key);

        return val;
    }

    void put(int key, int value) {
        if (m_cap == 0)
            return;

        int old_value = get(key);

        if (old_value != -1)
        {
            auto it = m.find(key);
            std::get<0>(it->second) = value;
            return;
        }

        if (m.size() == m_cap)
        {
            int freq_to_remove = freqs.begin()->first;
            int key_to_remove = freqs.begin()->second.front();
            eraseFreq(freq_to_remove, freqs.begin()->second.begin());

            m.erase(key_to_remove);
        }

        freqs[1].push_back(key);
        m[key] = make_tuple(value, 1, --freqs[1].end());
    }
};

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