Bug with std::deque?

Question

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.

Answer 1

From cppreference on deque::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.

All iterators. All of them. When you do this:

mydeque.erase(it++);

It doesn't matter that you post-incremented it, that new iterator is invalidated too. This is precisely why erase() returns:

Iterator following the last removed element. If the iterator pos refers to the last element, the end() iterator is returned.

So that you can do:

it = mydeque.erase(it); // erase old it, new it is valid

Although even better would be to avoid this source of error entirely by using the erase-remove idiom:

mydeque.erase(
   std::remove_if(mydeque.begin(), mydeque.end(), [](int i){return i%2 == 0; }),
   mydeque.end()
);

See also this question for more information about iterator invalidation.