LRU_CACHE

class LRUCache {
public:
    list<pair<int,int>> cache;

    unordered_map <int, list<pair<int,int>>:: iterator> mp; //key -- index in the cache

    int size;

    void refreshPosition(int key, int value) {
        cache.erase(mp[key]); //remove old position
        cache.push_front({key,value}); //push it in the fornt
        mp[key] = cache.begin(); // assign it to begin
    }

    LRUCache(int capacity) {
       this -> size = capacity;
    }

    int get(int key) {
        if(mp.find(key) != mp.end()) {
            refreshPosition(key, (*mp[key]).second);
            return (*mp[key]).second;

        }
        else {
            return -1;
        }
    }

    void put(int key, int value) {
        if(mp.find(key) != mp.end()) {
            refreshPosition(key, value);
        }
        else {
            cache.push_front(make_pair(key,value));
            mp[key] = cache.begin();

            if(mp.size() > size) {
                mp.erase(cache.back().first);
                cache.pop_back();
            }
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */