Got singular iterator error in looping with iterator and pop_back

Question

Giving the below code (say it's named deque.cpp)

#include <cstdio>
#include <deque>

int main()
{
  std::deque<int> d = {1, 2, 3};
  for (auto it = d.rbegin(); it != d.rend();) {
    printf("it: %d\n", *it);
    ++it;
    d.pop_back();
  }
  return 0;
}

Compile with g++ -std=c++11 -o deque deque.cpp, it runs well:

$ ./deque
it: 3
it: 2
it: 1

But if compile with -D_GLIBCXX_DEBUG (g++ -std=c++11 -o deque_debug deque.cpp -D_GLIBCXX_DEBUG, it gets below error:

$ ./deque_debug
it: 3
/usr/include/c++/4.8/debug/safe_iterator.h:171:error: attempt to copy-
    construct an iterator from a singular iterator.
...

It looks like the second loop's ++it is constructing from an singular iterator. But I think after the first loop's ++it, the iterator points to 2, and pop_back() should not invalidate it. Then why the error occurs?

Note: I know the code could be re-write as below:

  while (!d.empty()) {
    auto it = d.rbegin();
    printf("it: %d\n", *it);
    d.pop_back();
  }

And the error will be gone.

But I do want to know what exactly happens on the error code. (Does it mean the reverse iterator dose not actually point to the node I expect, but the one after it?)

---

Update: @Barry's answer resolved the question. Please let me put an extra related question: the code

  for (auto it = d.rbegin(); it != d.rend();) {
    printf("it: %d\n", *it);
    d.pop_back();
    ++it;   // <== moved below pop_back()
  }

is expected to be wrong, where ++it should be operating on an invalidated iterator. But why the code does not cause error?

Answer 1

The problem here arises from what reverse iterators actually are. The relevant relationship for a reverse iterator is:

For a reverse iterator r constructed from an iterator i, the relationship &*r == &*(i-1) is always true (as long as r is dereferenceable); thus a reverse iterator constructed from a one-past-the-end iterator dereferences to the last element in a sequence.

When we then do std::deque::pop_back(), we invalidate:

Iterators and references to the erased element are invalidated. The past-the-end iterator is also invalidated. Other references and iterators are not affected.

rbegin() is constructed from end(). After we increment it the first time, it will dereference to the 2 but its underlying base iterator is pointing to the 3 - that's the erased element. So the iterators referring to it include your now-advanced reverse iterator. That's why it's invalidated and that's why you're seeing the error that you're seeing.

Reverse iterators are complicated.

---

Instead of incrementing it, you could reassign it to rbegin():

for (auto it = d.rbegin(); it != d.rend();) {
    printf("it: %d\n", *it);
    d.pop_back();
    // 'it' and 'it+1' are both invalidated
    it = d.rbegin();
}

Answer 2

Erasing from the underlying container invalidates an iterator. Quoting from the rules:

Iterators are not dereferenceable if

• they are past-the-end iterators (including pointers past the end of an array) or before-begin iterators. Such iterators may be dereferenceable in a particular implementation, but the library never assumes that they are.
• they are singular iterators, that is, iterators that are not associated with any sequence. A null pointer, as well as a default-constructed pointer (holding an indeterminate value) is singular
• they were invalidated by one of the iterator-invalidating operations on the sequence to which they refer.

Your code causes the iterator to be invalidated by the pop_back operation, and thus as per the third point above, it becomes non dereferenceable.

In your while loop you're avoiding this problem by getting a (new) valid iterator in each loop repetition.