Why does a push_back on an std::list change a reverse iterator initialized with rbegin?

Question

According to some STL documentation I found, inserting or deleting elements in an std::list does not invalidate iterators. This means that it is allowed to loop over a list (from begin() to end()), and then add elements using push_front.

E.g., in the following code, I initialize a list with elements a, b and c, then loop over it and perform a push_front of the elements. The result should be cbaabc, which is exactly what I get:

std::list<std::string> testList;
testList.push_back("a");
testList.push_back("b");
testList.push_back("c");

for (std::list<std::string>::iterator itList = testList.begin(); itList != testList.end(); ++itList)
   testList.push_front(*itList);

for (std::list<std::string>::const_iterator itList = testList.begin(); itList != testList.end(); ++itList)
   std::cout << *itList << std::endl;

When I use reverse iterators (loop from rbegin() to rend()) and use push_back, I would expect similar behavior, i.e. a result of abccba. However, I get a different result:

std::list<std::string> testList;
testList.push_back("a");
testList.push_back("b");
testList.push_back("c");

for (std::list<std::string>::reverse_iterator itList = testList.rbegin(); itList != testList.rend(); ++itList)
   testList.push_back(*itList);

for (std::list<std::string>::const_iterator itList = testList.begin(); itList != testList.end(); ++itList)
   std::cout << *itList << std::endl;

The result is not abccba, but abcccba. That's right there is one additional c added.

It looks like the first push_back also changes the value of the iterator that was initialized with rbegin(). After the push_back it does not point anymore to the 3rd element in the list (which was previously the last one), but to the 4th element (which is now the last one).

I tested this with both Visual Studio 2010 and with GCC and both return the same result.

Is this an error? Or some strange behavior of reverse iterators that I'm not aware of?

Answer 1

I think to understand this, it's best to start by re-casting the for loop as a while loop:

typedef std::list<std::string> container;

container testList;
testList.push_back("a");
testList.push_back("b");
testList.push_back("c");

container::reverse_iterator itList = testList.rbegin(); 
while (itList != testList.rend()) {
    testList.push_back(*itList);
     ++itList;
}

Along with that, we have to understand how a reverse_iterator works in general. Specifically a reverse_iterator really points to the element after the one you get when you dereference it. end() yields an iterator to just after the end of the container -- but for things like arrays, there's no defined way to point to just before the beginning of a container. What C++ does instead is have the iterator start from just after the end, and progress to the beginning, but when you dereference it, you get the element just before where it actually points.

That means your code actually works like this:

After that, you get pretty much what you expect, pushing back B and then A, so you end up with ABCCCBA.

Answer 2

The standard says that iterators and references remain valid during an insert. It doesn't say anything about reverse iterators. :-)

The reverse_iterator returned by rbegin() internally holds the value of end(). After a push_back() this value will obviously not be the same as it was before. I don't think the standard says what it should be. Obvious alternatives include the previous last element of the list, or that it stays at the end if that is a fixed value (like a sentinel node).

---

Technical details: The value returned by rend() cannot point before begin(), because that is not valid. So it was decided that rend() should contain the value of begin() and all other reverse iterators be shifted one position further. The operator* compensates for this and accesses the correct element anyway.

First paragraph of 24.5.1 Reverse iterators says:

Class template reverse_iterator is an iterator adaptor that iterates from the end of the sequence defined by its underlying iterator to the beginning of that sequence. The fundamental relation between a reverse iterator and its corresponding iterator i is established by the identity:
&*(reverse_iterator(i)) == &*(i - 1).