lru cache gfg

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

class LRUCache {
private:
    int capacity;
    std::unordered_map<int, std::pair<int, std::list<int>::iterator>> cache;
    std::list<int> lruList;

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

    int get(int key) {
        auto it = cache.find(key);
        if (it != cache.end()) {
            // Move the accessed key to the front of the list
            lruList.erase(it->second.second);
            lruList.push_front(key);
            it->second.second = lruList.begin();
            return it->second.first;
        }
        return -1;
    }

    void put(int key, int value) {
        if (cache.size() == capacity) {
            // Remove the least recently used element from both the list and the cache
            int lruKey = lruList.back();
            lruList.pop_back();
            cache.erase(lruKey);
        }

        // Insert the new key-value pair into the cache and the front of the list
        lruList.push_front(key);
        cache[key] = {value, lruList.begin()};
    }
};

int main() {
    // Example usage of LRUCache
    LRUCache cache(2); // Capacity is 2

    cache.put(1, 1);   // Cache: {1=1}
    cache.put(2, 2);   // Cache: {2=2, 1=1}
    std::cout << cache.get(1) << std::endl;  // Output: 1
    cache.put(3, 3);   // Cache: {3=3, 2=2}
    std::cout << cache.get(2) << std::endl;  // Output: -1 (not found)
    cache.put(4, 4);   // Cache: {4=4, 3=3}
    std::cout << cache.get(1) << std::endl;  // Output: -1 (not found)
    std::cout << cache.get(3) << std::endl;  // Output: 3
    std::cout << cache.get(4) << std::endl;  // Output: 4

    return 0;
}