C++实现LRU缓存

Question

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

我的代码：

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

std::deque::erase(it) 使此双端队列中的所有迭代器都无效，而不仅仅是 it（除非 it 指的是第一个或最后一个元素）。 mp 保留现在无效的迭代器，随后尝试使用它们会出现未定义的行为。

相比之下，std::list::erase(it) 仅使 it 无效（或者更准确地说，所有引用 *it 的迭代器），而不是其他迭代器。

Answer 2

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

这是（可能）从 deque 的中间擦除一个值。

从dequeinvalidates all other existing iterators的中间擦除到出队。仅从 deque 的开头或结尾擦除不会使任何其他指向未擦除的 deque 值的迭代器无效。

此时，您 map 中的所有其他迭代器都不再有效。从这一点开始，通过您的 map 使用任何其他剩余的迭代器将成为未定义的行为。

您将需要完全重新设计您的实现。 deque 不能以这种方式使用。

C++实现LRU缓存

Implement LRU Cache in C++

c++

stl

deque

lru

data-structures