I was trying to implement LRU Cache for a Leetcode question. My final code is below and it works fine. However, my first choice was deque instead of list with exactly same procedure and I was getting wrong results while using deque. I saw the posts about “deque vs list” but I couldn’t figure out the reason. Why my code is working good for list and giving inconsistent results for deque?

class LRUCache 
{
public:
    list<int> dq;
    unordered_map <int, pair<int, list<int>::iterator>> mp;

    int size{};

    LRUCache(int capacity) 
    {
      size = capacity;  
    }
    

    int get(int key) 
    {
       int returnvalue{-1};
       
       if(mp.find(key) != mp.end())
       {
         returnvalue = mp[key].first;
         dq.erase(mp[key].second);
         dq.push_front(key);
         mp[key].second = dq.begin();
       }

      return returnvalue; 
    }
    
    void put(int key, int value) 
    {
       if(mp.find(key) != mp.end())
       { 
         dq.erase(mp[key].second);
         dq.push_front(key);
         mp[key] = {value,dq.begin()};
       }

       else
       {
         if(dq.size() < size)
         {
            dq.push_front(key);
            mp[key] = {value,dq.begin()};
         }
         else
         {
            mp.erase(dq.back());
            dq.pop_back();
            dq.push_front(key);
            mp[key] = {value,dq.begin()};         
         } 
       } 

    }
};