cache_lru.cpp

#include <iostream>
#include <unordered_map>
#include <list>
#include <optional>

using namespace std;

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

template<Hashable KeyT, class ValueT>
class LRUCache {
    using Entry = pair<KeyT, ValueT>;
    using Node = list<Entry>::iterator;

    std::size_t capacity {0};
    unordered_map<KeyT, Node> cache {};
    list<Entry> items {};

public:
    LRUCache(const std::size_t capacity) : capacity(capacity) {}

    std::optional<ValueT> get(const KeyT& key) {
        const auto it = cache.find(key);
        if (it != end(cache)) {
            items.splice(begin(items), items, it->second);
            return it->second->second;
        }
        return {};
    }

    void put(const KeyT& key, const ValueT& value) {
        if (auto it = cache.find(key); it != end(cache)) {
            items.splice(begin(items), items, it->second);
            it->second->second = value;
            return;
        }

        if (capacity == size(cache)) {
            cache.erase(items.back().first);
            items.pop_back();
        }
        items.push_front(make_pair(key, value));
        cache[key] = begin(items);
    }
};

int main() {
    auto cache = LRUCache<string, string>(2);

    cache.put("Response1", "Content1");
    cache.put("Response2", "Content2");  // Response1, Response2
    cout << *cache.get("Response1") << endl; // Content1

    cache.put("Response3", "Content3");  // Response3, Response1
    cout << *cache.get("Response2") << endl; // nil

    cache.put("Response4", "Content4"); // Response4, Response3

    cout << *cache.get("Response1") << endl; // nil
    cout << *cache.get("Response2") << endl; // nil
    cout << *cache.get("Response3") << endl; // Content3
    cout << *cache.get("Response4") << endl; // Content4
}