c++ - C++实现LRU缓存

Question

我曾尝试从 LeetCode 实现 LRU 缓存问题。
https://leetcode.com/problems/lru-cache/
缓存中的条目采用 {key, value} 对的形式。我面临着一个奇怪的问题。解决这个问题的方法是使用带有HashMap的双向链表。
对于双向链表，我所做的是在我的 C++ 代码中使用了双端队列 STL 容器而不是列表 STL 容器，但是我的代码在下面的测试用例中失败了。如果我只是用列表替换双端队列，代码就会被接受。有人可以帮忙看看在实现 LRU 缓存时使用 deque 有什么问题吗？我的代码使用 deque 也通过了许多测试用例。请帮忙。
我的代码:

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

失败的测试用例:

["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]```

Answer 1

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

这(可能)从 deque 的中间删除了一个值.
从 deque 的中间删除 invalidates all other existing iterators到出队。仅从 deque 的开头或结尾删除不会使未删除的任何其他迭代器无效 deque值。
此时，您 map 中的所有其他迭代器不再有效。从现在开始，使用任何其他剩余的迭代器，通过您的 map , 变成未定义的行为。
您将需要完全重新设计您的实现。 deque不能以这种方式使用。