Bug with std::deque?

I am trying to delete an element from a deque using a loop and an iterator. I am following online examples but seeing a bug.

I am using g++ (GCC) 4.8.3 20140911 (Red Hat 4.8.3-9).

Here is the code:

#include <iostream>
#include <deque>

using namespace std;

// Display the contents of a queue
void disp_deque(deque<int>& deque) {
  cout << "deque contains: ";
  for (auto itr = deque.begin(); itr!=deque.end(); ++itr)
    cout << *itr << ' ';
  cout << '\n';
}

int main(int argc, char** argv) {
  deque<int> mydeque;

  // Put 10 integers in the deque.
  for (int i=1; i<=10; i++) mydeque.push_back(i);
  disp_deque(mydeque);

  auto it = mydeque.begin(); 
  while (it!=mydeque.end()) {
    cout << "Checking " << *it << ',';
    // Delete even numbered values.
    if ((*it % 2) == 0) {
      cout << "Deleting " << *it << '\n';
      mydeque.erase(it++);
      disp_deque(mydeque);
    } else ++it;
  }
}

It is pretty straight forward - create a list of 10 elements and delete the even ones.

Notice the following (fluff excluded):

if ((*it % 2) == 0) {
  mydeque.erase(it++);
} else it++;

It is the recommended way to delete using an iterator so that your iterator does not get invalidated as mentioned in the link above.

However, when I run this, I get the following:

$ ./test
deque contains: 1 2 3 4 5 6 7 8 9 10 
Checking 1,Checking 2,Deleting 2
deque contains: 1 3 4 5 6 7 8 9 10 
Checking 3,Checking 4,Deleting 4
deque contains: 1 3 5 6 7 8 9 10 
Checking 5,Checking 6,Deleting 6
deque contains: 1 3 5 7 8 9 10 
Checking 7,Checking 8,Deleting 8
deque contains: 1 3 5 7 9 10 
Checking 10,Deleting 10
deque contains: 1 3 5 7 9 
Checking 10,Deleting 10
deque contains: 1 3 5 7 
Checking 0,Deleting 0
deque contains: 1 3 5 
Checking 0,Deleting 0
deque contains: 1 3 
Checking 0,Deleting 0
deque contains: 1 
Checking 0,Deleting 0
deque contains: 
Checking 0,Deleting 0
Segmentation fault (core dumped)

Looking through it, it seems pretty good up until it deletes 8. In fact, number 9 is skipped altogether and never checked! What I expect should happen is this:

$ ./test
deque contains: 1 2 3 4 5 6 7 8 9 10 
Checking 1,Checking 2,Deleting 2
deque contains: 1 3 4 5 6 7 8 9 10 
Checking 3,Checking 4,Deleting 4
deque contains: 1 3 5 6 7 8 9 10 
Checking 5,Checking 6,Deleting 6
deque contains: 1 3 5 7 8 9 10 
Checking 7,Checking 8,Deleting 8
deque contains: 1 3 5 7 9 10 
Checking 9,Checking 10,Deleting 10
deque contains: 1 3 5 7 9

In fact, this is exactly what I get when I change the code to this:

if ((*it % 2) == 0) {
  it=mydeque.erase(it);
} else it++;

So, why does one method work, but the other not? Can anyone explain it?

Even if I create a temporary iterator to delete, I see the exact same problem output:

  while (it!=mydeque.end()) {
    cout << "Checking " << *it << ',';
    auto tmp_it = it++;
    // Delete even numbered values.
    if ((*tmp_it % 2) == 0) {
      cout << "Deleting " << *tmp_it << '\n';
      cout << "IT before delete: " << *it << '\n';
      mydeque.erase(tmp_it);
      cout << "IT after delete: " << *it << '\n';
      disp_deque(mydeque);
    } 
  }

Here I store a copy of it in tmp_it and then increment it. I added some more debug statements and saw some really weird stuff:

...
deque contains: 1 3 5 6 7 8 9 10 
Checking 5,Checking 6,Deleting 6
IT before delete: 7
IT after delete: 7
deque contains: 1 3 5 7 8 9 10 
Checking 7,Checking 8,Deleting 8
IT before delete: 9
IT after delete: 10
deque contains: 1 3 5 7 9 10 
Checking 10,Deleting 10
IT before delete: 10
IT after delete: 10
...

However, the deletion of element 8 makes it point to element 10, skipping 9! On previous deletes, it was pointing to the previous element (e.g. when 6 was deleted, it was pointing to 7 before and after the delete).

I looked up the implementation of deque and see under "Iterator Validity" the following (emphasis mine):

Iterator validity If the erasure operation includes the last element in the sequence, the end iterator and the iterators, pointers and references referring to the erased elements are invalidated. If the erasure includes the first element but not the last, only those referring to the erased elements are invalidated. If it happens anywhere else in the deque, all iterators, pointers and references related to the container are invalidated.

So does that mean that in my code, my iterator is being invalidated even though I did a post increment on it before it is deleted? i.e. an iterator other than the one I deleted is being invalidated?

If so, then that it fine, but it seems like a little known bug. It means that common implementations of iterator deletion within a loop are not valid when using deque.

Solution

The code you quoted is for associative containers only (set, map etc.).

Scott Meyers's Effective STL Item 9 (aptly named "Choose carefully among erasing options") shows how it's done for sequence containers (vector, deque, string)

for (SeqContainer<int>::iterator it = c.beqin(); it != c.end();) {
    if (predicate(*it)){
        it = c.erase(it); // keep it valid by assigning
    }                     // erase's return value to it
    else ++it;
}

Here, the erase() return value is exactly what we need: it's a valid iterator pointing to the element following the erased element once the erase has been accomplished.