Perché un push_back su un elenco std :: cambia un iteratore inverso inizializzato con rbegin?

Question

Secondo alcuni documenti STL che ho trovato, l'inserimento o l'eliminazione di elementi in un elenco std :: non invalida gli iteratori. Ciò significa che è consentito eseguire il loop su un elenco (da begin() a end()) e quindi aggiungere elementi utilizzando push_front.

Ad esempio, nel seguente codice, inizializzo un elenco con gli elementi a, b e c, quindi eseguo il loop su di esso ed eseguo un push_front degli elementi. Il risultato dovrebbe essere cbaabc, che è esattamente quello che ottengo:

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; 

Quando uso iteratori inversi (anello rbegin()-rend()) e usare push_back, mi sarei aspettato un comportamento simile, vale a dire il risultato di abccba. Tuttavia, ottengo un risultato diverso:

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; 

il risultato non è abccba, ma abcccba. Esatto, c'è una c aggiuntiva aggiunta.

Sembra che il primo push_back modifichi anche il valore dell'iteratore inizializzato con rbegin(). Dopo il push_back non punta più al terzo elemento della lista (che era in precedenza l'ultimo), ma al quarto elemento (che ora è l'ultimo).

Ho provato questo con Visual Studio 2010 e con GCC ed entrambi restituiscono lo stesso risultato.

È un errore? O qualche strano comportamento di iteratori rovesciati di cui non sono a conoscenza?

Answer 1

Lo standard dice che iteratori e riferimenti rimangono validi durante un inserto. Non dice nulla degli iteratori inversi. :-)

Il reverse_iterator restituito da rbegin() contiene internamente il valore di end(). Dopo un push_back() questo valore ovviamente non sarà lo stesso di prima. Non penso che lo standard dica cosa dovrebbe essere. Le alternative ovvie includono l'ultimo elemento precedente dell'elenco o che rimane alla fine se questo è un valore fisso (come un nodo sentinella).

---

Dettagli tecnici: Il valore restituito da rend() non può puntare prima begin(), perché non è valida. Quindi è stato deciso che rend() deve contenere il valore di begin() e tutti gli altri iteratori inversi devono essere spostati di una posizione ulteriormente. Il operator* compensa questo e accede comunque l'elemento corretto.

primo comma 24.5.1 iteratori Reverse dice:

modello Classe reverse_iterator è un adattatore iteratore che scorre dalla fine della sequenza definita dal suo iteratore sottostante l'inizio di quella sequenza. La relazione fondamentale tra un iteratore inverso e il relativo iteratore i è stabilito dall'identità:
&*(reverse_iterator(i)) == &*(i - 1).

Answer 2

Provare a utilizzare un iteratore per entrambi. Prova:

std::list<std::string>::iterator i = testList.end(); 

e invertire attraverso con --I

Answer 3

penso di capire questo, è meglio iniziare da ri-fusione del ciclo for come un ciclo while:

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

Insieme a questo, dobbiamo capire come funziona un reverse_iterator lavori in generale. Nello specifico un reverse_iterator punta davvero all'elemento dopo lo quello che si ottiene quando lo si denigra. end() restituisce un iteratore al solo dopo il alla fine del contenitore, ma per elementi come gli array, non esiste un modo definito di puntare appena prima dell'inizio di un contenitore. C++ invece ha l'iteratore che inizia appena dopo la fine, e progredisce all'inizio, ma quando lo si denigra, si ottiene l'elemento solo prima di dove effettivamente punta.

Questo significa che il codice in realtà funziona così:

Dopo di che, si ottiene più o meno quello che ci si aspetta, spingendo indietro B e poi A, così si finisce con ABCCCBA.