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

Question

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

Протестировано на 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
}

9

c++reverse-iterator stdlist

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

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

#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

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

19