q1lrucache.cpp

#include <unordered_map>
#include <list>

class LRUCache {
public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = mp.find(key);
        if (it == mp.end()) return -1;
        lst.splice(lst.begin(), lst, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = mp.find(key);
        if (it != mp.end()) {
            it->second->second = value;
            lst.splice(lst.begin(), lst, it->second);
            return;
        }

        if (lst.size() == cap) {
            int oldKey = lst.back().first;
            mp.erase(oldKey);
            lst.pop_back();
        }

        lst.push_front({key, value});
        mp[key] = lst.begin();
    }

private:
    int cap;
    std::list<std::pair<int,int>> lst;
    std::unordered_map<int, std::list<std::pair<int,int>>::iterator> mp;
};