Perché la rimozione dell'elemento _primo_ di un elenco invalida `.rend()`?

Question

Testato su Mac OS X utilizzando XCode 4.6.

codice Questo esempio mostra rimozione dell'ultimo elemento di un std::list lavori come mi aspettavo: un riferimento iteratore list::end() è ancora "1 dopo la fine" ed è ancora valido, anche attraverso la rimozione dell'ultimo elemento.

Ma il secondo esempio contrasta la mia intuizione. Rimozione del prima elemento della lista modifiche list::rend(), che ho pensato fosse "1 dopo l'inizio".

La mia aspettativa era sbagliata? Perché era sbagliato? Perché il tuo riferimento a "1 alla fine" attraverso la cancellazione dell'ultimo elemento rimane valido (non dovrebbe?), Ma un riferimento a "1 davanti all'inizio (.rend()) non è più valido dopo la rimozione dell'elemento frontale?

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

Ciò è dovuto al fatto che un iteratore inverso ha una logica di riferimento leggermente diverso rispetto a un iteratore regolare:. punta ad un elemento, ma quando dereferenziati, produce un riferimento all'elemento precedente

Lo vedrai facilmente se provi quanto segue:

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

L'output dovrebbe essere:

3 
2 

Quando un iteratore inverso fisicamente punti ad un certo elemento, esso logicamente punta all'elemento che lo precede. Così, un iteratore inverso fisicamente punta all'elemento in una raccolta con indice i, quando dereferenziato, rese (un riferimento a) l'elemento con indice i-1:

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

Questo è il motivo per cui un rendimento iteratore da rend() effettivamente punta al primo elemento di una raccolta e non a quello precedente al primo elemento. Rimuovendo il primo elemento, quindi, lo invalida.

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

Questo non si applica solo agli elenchi, ma a tutte le raccolte che offrono iteratori bidirezionali.