Design with hash maps (Arrays & Hashing Sub-pattern)

// LRU-style cache: the map finds a key in O(1), the list keeps recency order.
class Cache {
    int capacity;
    list<pair<int, int>> order;                               // front = most recent
    unordered_map<int, list<pair<int, int>>::iterator> where; // key -> its node in the list

public:
    Cache(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto it = where.find(key);
        if (it == where.end()) return -1;
        order.splice(order.begin(), order, it->second);  // move to front, O(1)
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = where.find(key);
        if (it != where.end()) {                          // existing key: update + move to front
            it->second->second = value;
            order.splice(order.begin(), order, it->second);
            return;
        }
        if ((int)order.size() == capacity) {              // full: evict the least recent
            where.erase(order.back().first);
            order.pop_back();
        }
        order.emplace_front(key, value);
        where[key] = order.begin();
    }
};