c++ - 为什么在std::deque.erase()上引发异常？

Question

尝试通过迭代器从deque中删除元素时抛出此错误。错误是使用VS2017“无法寻求值初始化的迭代器”。我不知道为什么会这样，std::deque是否不是不会使push_front() / push_back()上的迭代器无效的双向链表？

class deque2 {
public:
    bool enqueue(int val) {
        if (mp.find(val) != mp.end()) {
            return false;
        }
        dq.push_front(val);
        mp[val] = dq.begin();
        return true;
    }

    int dequeue() {
        if (dq.size() == 0) {
            return -1;
        }

        int res = dq.back();
        mp.erase(res);
        dq.pop_back();
        return res;
    }

    void erase(int val) {
        auto it = mp.find(val);
        if (it != mp.end()) {
            dq.erase(it->second); // exception 
            mp.erase(val);
        }
    }
private:
    deque<int> dq;
    unordered_map<int, deque<int>::iterator> mp;
};

Answer 1

isn't std::deque a doubly linked list

不它不是。如 documentation中所述

std::deque (double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. In addition, insertion and deletion at either end of a deque never invalidates pointers or references to the rest of the elements.

重点是我的。请注意，它说的是指针或引用不是无效的，不是迭代器。并且有关 std::deque::push_front()的文档明确指出:

All iterators, including the past-the-end iterator, are invalidated. No references are invalidated.

至于您要实现的逻辑，我建议您使用 boost::multi_index，因为它允许具有不同访问条件的单个容器，并且您不必保持2个容器同步。可以找到文件 here