Implement LRU Cache in C++

I have tried implementing LRU Cache Problem from LeetCode. https://leetcode.com/problems/lru-cache/ The entries in cache are in the form of {key, value} pairs. There is a weird issue that I am facing. To solve this problem, the approach is to use to a Doubly linked list with a HashMap. For Doubly linked list, What I have done is used a deque STL container instead of list STL container in my C++ code, but my code fails on below test case. If I just replace deque with list, the code got accepted. Can someone please help as what is the issue with using deque in implementing a LRU Cache. Also many test cases have passed with my code using deque. please help.

My Code :

class LRUCache {
public:
    unordered_map<int, pair<deque<int>::iterator,int>> mp; // {key, pair<iterator_position_in_deque, value>}; // iterator is the position in the deque where the key is stored.
    deque<int> dq; // {key} storing only keys.
    int size;
    int curr_size;
    LRUCache(int capacity) {
        curr_size = 0;
        size = capacity;
        dq.clear();
        mp.clear();
    }
    
    int get(int key) {
        if(mp.find(key) == mp.end()) {
            return -1;
        }
        
        // below 3 lines are same as in put function
        dq.erase(mp[key].first);
        dq.push_front(key);
        mp[key].first = dq.begin();
        
        return mp[key].second;
    }
    
    void put(int key, int value) {
        if(mp.find(key) != mp.end()) { // if key present in cache
            
            dq.erase(mp[key].first);
            dq.push_front(key);
            mp[key].first = dq.begin();
            
            mp[key].second = value; // update the new value to that key
        } else { // if key not present in our map and deque afterwards
            if (curr_size < size) {
                dq.push_front(key);
                mp[key] = make_pair(dq.begin(), value);
                curr_size++;
            } else if (curr_size == size) {
                mp.erase(dq.back()); // element will the key as deque stores key
                dq.pop_back();
                dq.push_front(key);
                mp[key] = make_pair(dq.begin(), value);
            }
        }
    }
    
};

/**
 * 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);
 */

Test Case on which it failing :

["LRUCache","put","put","put","put","put","get","put","get","get","put","get","put","put","put","get","put","get","get","get","get","put","put","get","get","get","put","put","get","put","get","put","get","get","get","put","put","put","get","put","get","get","put","put","get","put","put","put","put","get","put","put","get","put","put","get","put","put","put","put","put","get","put","put","get","put","get","get","get","put","get","get","put","put","put","put","get","put","put","put","put","get","get","get","put","put","put","get","put","put","put","get","put","put","put","get","get","get","put","put","put","put","get","put","put","put","put","put","put","put"]
[[10],[10,13],[3,17],[6,11],[10,5],[9,10],[13],[2,19],[2],[3],[5,25],[8],[9,22],[5,5],[1,30],[11],[9,12],[7],[5],[8],[9],[4,30],[9,3],[9],[10],[10],[6,14],[3,1],[3],[10,11],[8],[2,14],[1],[5],[4],[11,4],[12,24],[5,18],[13],[7,23],[8],[12],[3,27],[2,12],[5],[2,9],[13,4],[8,18],[1,7],[6],[9,29],[8,21],[5],[6,30],[1,12],[10],[4,15],[7,22],[11,26],[8,17],[9,29],[5],[3,4],[11,30],[12],[4,29],[3],[9],[6],[3,4],[1],[10],[3,29],[10,28],[1,20],[11,13],[3],[3,12],[3,8],[10,9],[3,26],[8],[7],[5],[13,17],[2,27],[11,15],[12],[9,19],[2,15],[3,16],[1],[12,17],[9,1],[6,19],[4],[5],[5],[8,1],[11,7],[5,2],[9,28],[1],[2,2],[7,4],[4,22],[7,24],[9,26],[13,28],[11,26]] ```

Output :
```[null,null,null,null,null,null,-1,null,19,17,null,-1,null,null,null,-1,null,-1,5,-1,12,null,null,3,5,5,null,null,1,null,-1,null,30,5,30,null,null,null,-1,null,-1,24,null,null,18,null,null,null,null,-1,null,null,18,null,null,11,null,null,null,null,null,18,null,null,-1,null,4,29,30,null,12,11,null,null,null,null,29,null,null,null,null,17,22,18,null,null,null,-1,null,null,null,-1,null,null,null,29,18,18,null,null,null,null,-1,null,null,null,null,null,null,null]```

Expected Output :
```[null,null,null,null,null,null,-1,null,19,17,null,-1,null,null,null,-1,null,-1,5,-1,12,null,null,3,5,5,null,null,1,null,-1,null,30,5,30,null,null,null,-1,null,-1,24,null,null,18,null,null,null,null,-1,null,null,18,null,null,11,null,null,null,null,null,18,null,null,-1,null,4,29,30,null,12,11,null,null,null,null,29,null,null,null,null,17,22,18,null,null,null,-1,null,null,null,-1,null,null,null,29,18,18,null,null,null,null,-1,null,null,null,null,null,null,null]```

Solution

dq.erase(mp[key].first);

This is (potentially) erases a value from the middle of the deque.

Erasing from a middle of a deque invalidates all other existing iterators to the dequeue. Only erasing from the beginning or the end of a deque does not invalidate any other iterators to the non-erased deque values.

At this point, all other iterators in your map are no longer valid. From this point on, using any other remaining iterators, via your map, becomes undefined behavior.

You will need to completely redesign your implementation. deque cannot be used in this manner.