Почему удаление элемента _first_ из списка делает недействительным `.rend()`?

Question

Протестировано на Mac OS X с использованием XCode 4.6.

Этот пример кода показывает удаление последнего элемента std::list работает как я ожидал: ссылка на итератор list::end() по-прежнему "1 за концом" и остается в силе даже после удаления последнего элемента.

Но второй пример противоречит моей интуиции. Удаление первого элемента списка измененийlist::rend(), который я думал, был "1 мимо начала".

Мои ожидания были неверны? Почему это было неправильно? Почему ваша ссылка на "1 за концом" посредством удаления последнего элемента остается действительной (не так ли?), Но ссылка на "1 перед началом (.rend()) становится недействительным после удаления переднего элемента?

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

Это связано с тем, что обратный итератор имеет немного иную логику ссылок, чем обычный итератор: он указывает на элемент, но при разыменовании он дает ссылку на предыдущий элемент.

Это легко увидеть, если вы попробуете следующее:

#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;
}

Выход должен быть:

3
2

Когда обратный итератор физически указывает на определенный элемент, он логически указывает на предшествующий ему элемент. Таким образом, обратный итератор физически указывает на элемент в коллекции с индексом iпри разыменовании возвращает (ссылку на) элемент с индексом i-1:

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

Это причина, по которой итератор возвращается rend() фактически указывает на первый элемент в коллекции, а не на элемент перед первым элементом. Поэтому удаление первого элемента делает его недействительным.

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

Это относится не только к спискам, но и ко всем коллекциям, которые предлагают двунаправленные итераторы.