c++ - Why does removing the _first_ element of a list invalidate `.rend()`?

Question

Tested on Mac OS X using XCode 4.6.

This example code shows removing the last element of an std::list works as I expected: an iterator reference to list::end() is still "1 past the end" and is still valid, even through removal of the last element.

But the second example counters my intuition. Removing the first element of the list changes list::rend(), which I thought was "1 past the beginning".

Was my expectation wrong? Why was it wrong? Why does your reference to "1 past the end" through deletion of the last element remain valid (should it not?), but a reference to "1 in front of the beginning (.rend()) becomes invalid after removal of the front element?

void printList( list<int>& os )
{
  for( int& i : os )
    printf( "%d ", i ) ;
  puts("");
}

void testList()
{
  list< int > os ;
  os.push_back( 1 ) ;
  os.push_back( 2 ) ;
  os.push_back( 3 ) ;
  os.push_back( 4 ) ;
  os.push_back( 5 ) ;  

  // Forward iterators:  reference to .end() not invalidated when remove last elt.
  list<int>::iterator fwdEnd = os.end() ;
  printList( os ) ;
  os.erase( --os.end() ) ; // remove the 5 (last elt)
  printList( os ) ;
  if( fwdEnd == os.end() )  puts( "YES, fwdEnd==os.end() still, iterators not invalidated" ) ;  // I get __this__ result
  else puts( "NO: fwdEnd INVALIDATED" ) ;



  list<int>::reverse_iterator revEnd = os.rend() ;
  // remove the front element
  printList( os ) ;
  os.erase( os.begin() ) ; // removes the 1
  printList( os ) ;
  if( revEnd == os.rend() )  puts( "YES revEnd is still valid" ) ;
  else  puts( "NO: revEnd NOT valid" ) ; // I get __this__ result
}

Answer 1

This is due to the fact that a reverse iterator has a slightly different referencing logic than a regular iterator: it points to an element, but when dereferenced, it yields a reference to the previous element.

You will easily see this if you try the following:

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> v = { 1, 2, 3, 4, 5, 6 };
    auto i = find(begin(v), end(v), 3);
    cout << *i << endl;

    vector<int>::const_reverse_iterator ri(i);
    cout << *ri << endl;
}

The output should be:

3
2

When a reverse iterator physically points to a certain element, it logically points to the element which precedes it. Thus, a reverse iterator physically pointing to the element in a collection with index i, when dereferenced, yields (a reference to) the element with index i-1:

                       i, *i
                       |
    -      1     2     3     4     5     6     -
                 |     | 
                 *ri   ri

This is the reason why an iterator return by rend() actually points to the first element in a collection, and not to the one before the first element. Removing the first element, therefore, invalidates it.

           begin, *begin                       end, *end
           |                                   |
    -      1     2     3     4     5     6     -
    |      |                             |     |
*rend      rend                    *rbegin     rbegin

This does not apply only to lists, but to all collections which offer bidirectional iterators.