Why the exception is thrown on std::deque.erase()?

Question

This throws when trying to remove element from deque via iterator. The error is "can not seek value-initialized iterator" using VS2017. I wonder why this is happening, isn't std::deque a doubly linked list that does not invalidate iterators on 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;
};

"isn't std::deque a doubly linked list" no it is not. Why would somebody put the same container with different names in the library? — Slava, Aug 10 '20 at 23:04
Note that `return -1;` is probably not a good error handling solution. `deque2` can contain that value in its normal use. — François Andrieux, Aug 10 '20 at 23:06
@FrançoisAndrieux actually they do https://en.cppreference.com/w/cpp/container/deque/push_back — Slava, Aug 10 '20 at 23:07
sorry for being dumb. should have been used here. https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl has the internal explanation how deque works in STL under the hood — dgrandm, Aug 10 '20 at 23:10
@Slava Thanks, I guess I was thinking of pointers to elements. — François Andrieux, Aug 10 '20 at 23:22

Slava · Answer 1 · 2020-08-10T23:15:44.557

isn't std::deque a doubly linked list

No it is not. As stated in 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.

emphasis is mine. Note that it says that pointer or references not invalidated, not iterators. And documentations on std::deque::push_front() clearly says so:

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

As for the logic you are trying to implement I would recommend to use boost::multi_index as it allows single container with different access criteria and you do not have to maintain 2 containers in sync. Documentation can be found here

Why the exception is thrown on std::deque.erase()?

1 Answers1