Warum ändert ein push_back auf einer std :: list einen umgekehrten Iterator, der mit rbegin initialisiert wurde?

Question

Laut einiger STL-Dokumentation, die ich gefunden habe, das Einfügen oder Löschen von Elementen in einer std :: list Iteratoren nicht ungültig. Das bedeutet, dass eine Schleife über eine Liste (von begin() bis end()) möglich ist. Fügen Sie dann Elemente mithilfe von push_front hinzu.

Zum Beispiel initialisiere ich im folgenden Code eine Liste mit den Elementen a, b und c, kreise dann darüber und führe eine push_front der Elemente aus. Das Ergebnis sollte cbaabc sein, was genau das ist, was ich bekommen:

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; 

Wenn ich Reverse-Iteratoren verwenden (Schleife rbegin()-rend()) und verwenden push_back, ich würde erwarten, dass ein ähnliches Verhalten, das heißt aufgrund der abccba. Ich erhalte jedoch ein anderes Ergebnis:

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; 

Das Ergebnis nicht abccba, aber abcccba. Das ist richtig, da ist ein zusätzliches c hinzugefügt.

Es sieht so aus, als ob die erste push_back auch den Wert des Iterators ändert, der mit rbegin() initialisiert wurde. Nach dem push_back zeigt es nicht mehr auf das dritte Element in der Liste (welches vorher das letzte war), sondern auf das vierte Element (welches nun das letzte ist).

Ich habe dies mit Visual Studio 2010 und mit GCC getestet und beide das gleiche Ergebnis zurückgeben.

Ist das ein Fehler? Oder ein seltsames Verhalten von Reverse-Iteratoren, die mir nicht bekannt sind?

Answer 1

Die Norm sagt, dass Iteratoren und Verweise während eines Einsatzes gültig bleiben. Es sagt nichts über umgekehrte Iteratoren aus. :-)

Die reverse_iterator, die von rbegin() zurückgegeben wird, enthält intern den Wert end(). Nach einem push_back() wird dieser Wert natürlich nicht mehr so ​​sein wie vorher. Ich denke nicht, dass der Standard sagt, was es sein soll. Offensichtliche Alternativen schließen das vorhergehende letzte Element der Liste ein oder dass es am Ende bleibt, wenn das ein fester Wert ist (wie ein Sentinel-Knoten).

---

Technische Details: Der Wert von rend() zurückgegeben wird, kann nicht vor begin() Punkt, denn das ist nicht gültig ist. So wurde entschieden, dass rend() den Wert begin() enthalten sollte und alle anderen Rückwärtsiteratoren um eine Position weiter verschoben sein sollten. Die operator* kompensiert dies und greift trotzdem auf das richtige Element zu.

Absatz 24.5.1 Reverse-Iteratoren sagt:

Vorlage Klasse reverse_iterator ist ein Iterator-Adapter, der iteriert vom Ende der Sequenz zu Beginn durch die ihr zugrunde liegenden Iterator definiert dieser Sequenz. Die grundlegende Beziehung zwischen einem umgekehrten Iterator und seinem entsprechenden Iterator i wird durch die Identität:
&*(reverse_iterator(i)) == &*(i - 1) hergestellt.

Answer 2

Versuchen Sie, einen Iterator für beide zu verwenden. Versuchen:

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

und rückwärts durch mit --i

Answer 3

Ich denke, dies zu verstehen, ist es am besten durch erneutes Gießen der for Schleife als while Schleife zu starten:

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

Zusammen mit, dass müssen wir verstehen, wie ein reverse_iterator Werke im Allgemeinen. Insbesondere zeigt ein reverse_iterator wirklich auf das Element nach die Sie erhalten, wenn Sie es dereferenzieren. end() ergibt einen Iterator nur nach das Ende des Containers - aber für Dinge wie Arrays, gibt es keine definierte Möglichkeit, direkt vor dem Anfang eines Containers zu zeigen. Was C++ dagegen tut, ist, dass der Iterator unmittelbar nach dem Ende beginnt und zum Anfang fortschreitet, aber wenn Sie es dereferenzieren, erhalten Sie das Element nur vor, wo es tatsächlich zeigt.

Das bedeutet, dass Ihr Code tatsächlich funktioniert wie folgt aus:

Danach werden Sie ziemlich viel bekommen, was Sie erwarten, B zurückschieben und dann A, so dass Sie mit ABCCCBA enden.