cache_lfu.cpp

#include <iostream>
#include <stdexcept>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <optional>
#include <cassert>

using namespace std;

struct KeyIsMissingException : public std::runtime_error {
    KeyIsMissingException() : std::runtime_error("Key is missing") {}
};

template <class T>
concept Hashable = requires(T param) { std::hash<T>()(param); };

template<Hashable KeyT, class ValT>
class LFUCache {
    using ValPtrT = unique_ptr<ValT>;

    int capacity {0};
    int minFreq {0};
    unordered_map<KeyT, ValPtrT> values;
    unordered_map<KeyT, int> freqs;
    unordered_map<int, unordered_set<KeyT>> keys;

    LFUCache(const int capacity) : capacity{capacity} {

    }

public:
    static LFUCache create(const int capacity) {
        return LFUCache(capacity);
    }

    bool Contains(const KeyT& key) const {
        return values.contains(key);
    }

    const ValT& Get(const KeyT& key) {
        if (!values.contains(key)) {
            throw KeyIsMissingException();
        }
        update(key, std::move(values[key]), freqs[key]);
        return *values[key];
    }

    template<class T>
    void Put(const KeyT& key, T&& value) {
        static_assert(std::is_convertible_v<std::decay_t<T>, ValT>);
        if (freqs.contains(key)) {
            const int freq = freqs[key];
            update(key, make_unique<ValT>(std::forward<T>(value)), freq);
        } else {
            if (size(values) >= capacity) {
                evict();
            }
            values[key] = make_unique<ValT>(std::forward<T>(value));
            freqs[key] = 1;
            keys[1].insert(key);
            minFreq = 1;
        }
    }

private:
    void update(const KeyT& key, ValPtrT value, const int freq) {
        keys[freq].erase(key);
        if (keys[freq].empty()) {
            keys.erase(freq);
            if (minFreq == freq) {
                minFreq += 1;
            }
        }

        values[key] = std::move(value);
        freqs[key] = freq + 1;
        keys[freq + 1].insert(key);
    }

    void evict() {
        assert(!keys[minFreq].empty());
        const auto key = *begin(keys[minFreq]);
        keys[minFreq].erase(begin(keys[minFreq]));
        if (keys[minFreq].empty()) {
            keys.erase(minFreq);
        }
        values.erase(key);
        freqs.erase(key);
    }
};

int main() {
    auto lfu = LFUCache<int, string>::create(3);

    lfu.Put(1, "A");
    lfu.Put(2, "B");

    assert(lfu.Get(1) == "A");

    lfu.Put(3, "C");

    assert(lfu.Get(2) == "B");

    lfu.Put(4, "D");

    assert(!lfu.Contains(3));
    assert(lfu.Get(1) == "A");
    assert(lfu.Get(2) == "B");
    assert(lfu.Get(4) == "D");

    cout << "OK" << endl;
}