c++ - 我的 LRU 有什么问题？我错误地使用了 std::deque 吗？

Question

我对此感到非常沮丧，现在我仍然完全不知道为什么我会出错。所以我正在按如下方式执行 LRU 实现:

#include <iostream>
#include <unordered_map>
#include <deque>
#include <list>

using namespace std;

class LRUCache {
public:
    LRUCache(int capacity) : cap(capacity) {
        cache.clear();
        pos_map.clear();
    }
    void check_recent() {
        cout << "recent: ";
        for (auto it : cache)
            cout << it << " ";
        cout << endl;
    }
    int get(int key) {
        cout << "get: " << key << " ; ";
        auto it = pos_map.find(key);
        if (it != pos_map.end()) {
            cache.erase(it->second.second);
            cache.push_front(key);
            pos_map[key].second = cache.begin();
            check_recent();
            return pos_map[key].first;
        } 
        check_recent();
        return -1;
    }
    
    void put(int key, int value) {
        cout << "put: " << key << ", " << value << " ; ";
        auto it = pos_map.find(key);
        if (it != pos_map.end()) {
            pos_map[key].first = value;
            cache.erase(it->second.second);
            cache.push_front(key);
            pos_map[key].second = cache.begin();
        } else {
            cache.push_front(key);
            if (cache.size() > cap) {
                int remove = cache.back();
                cache.pop_back();
                pos_map.erase(remove);
            }
            pos_map[key] = make_pair(value, cache.begin());
        }
        
        check_recent();
        return ;
    }
private:
    int cap;
    deque<int> cache; // deque of keys
    unordered_map<int, pair<int, deque<int>::iterator>> pos_map;
    // <key, <value, iter>>
};

int main()
{
    cout<<"Hello World\n";
    LRUCache* obj = new LRUCache(10);
    obj->put(10, 13);
    obj->put(3, 17);
    obj->put(6, 11);
    obj->put(10, 5);
    obj->put(9, 10);
    obj->get(13);
    obj->put(2, 19);
    obj->get(2);
    obj->get(3);
    obj->put(5, 25);
    obj->put(9, 22);
    obj->put(5, 5);
    obj->put(1, 13);
    obj->put(9, 12);
    return 0;
}

然后我得到以下输出:

Hello World
put: 10, 13 ; recent: 10 
put: 3, 17 ; recent: 3 10 
put: 6, 11 ; recent: 6 3 10 
put: 10, 5 ; recent: 10 6 3 
put: 9, 10 ; recent: 9 10 6 3 
get: 13 ; recent: 9 10 6 3 
put: 2, 19 ; recent: 2 9 10 6 3 
get: 2 ; recent: 2 9 10 6 3 
get: 3 ; recent: 3 2 9 10 6 
put: 5, 25 ; recent: 5 3 2 9 10 6 
put: 9, 22 ; recent: 9 5 3 2 10 6 
put: 5, 5 ; recent: 5 9 3 2 10 6 
put: 1, 13 ; recent: 1 5 9 3 2 10 6 
put: 9, 12 ; recent: 9 1 "9" 3 2 10 6 

这个错误“9”花了我一个小时来找出原因，但还是徒劳。但问题是，如果我将代码中的所有 std::deque 更改为 std::list，结果与我的预期相同:

put: 9, 12 ; recent: 9 1 "5" 3 2 10 6 

那么 std::deque::erase 到底发生了什么？我做错什么了吗？有人可以指导我或给我一些线索吗？非常感谢

Answer 1

So what the heck is going on with std::deque::erase? Did I do something wrong?

你有两个数据结构，其中一个映射到另一个的迭代器:

    deque<int> cache; // deque of keys
    unordered_map<int, pair<int, deque<int>::iterator>> pos_map;

如果迭代器要出队，则the invalidation rules of erase状态

All iterators and references are invalidated, unless the erased elements are at the end or the beginning of the container, in which case only the iterators and references to the erased elements are invalidated.

然而，for list我们有

References and iterators to the erased elements are invalidated. Other references and iterators are not affected.