LRU

class LRUCache
{
    public:
    list<int> dq;
    int size;
    unordered_map<int,pair<list<int>::iterator,int>>m;
    public:
    //Constructor for initializing the cache capacity with the given value.
    LRUCache(int cap)
    {
        // code here
        size = cap;
    }
    
    //Function to return value corresponding to the key.
     int get(int key)
    {
        // your code here
        if(m.find(key)==m.end())
        return -1;
        else
        {
            dq.erase(m[key].first);
            dq.push_front(key);
            m[key].first=dq.begin();
            return m[key].second;
        }
    }
    
    //Function for storing key-value pair.
 void set(int key, int value)
    {
        // your code here   
            
            if (m.find(key) == m.end()) {
        // cache is full
        if (dq.size() == size) {
            // delete least recently used element
            int last = dq.back();
 
            // Pops the last elmeent
            dq.pop_back();
 
            // Erase the last
            m.erase(last);
        }
    }else
    dq.erase(m[key].first);
    
            dq.push_front(key);
            m[key].first=dq.begin();
            m[key].second=value;
    }
};