geeksforgeeks - list iterator c++

¿Por qué un push_back en un std:: list cambia un iterador inverso inicializado con rbegin?

Question

Según la documentación de STL que encontré, la inserción o eliminación de elementos en una lista std :: no invalida los iteradores. Esto significa que se le permite recorrer una lista (desde begin() hasta end() ), y luego agregar elementos usando push_front.

Por ejemplo, en el siguiente código, inicializo una lista con los elementos a, byc, luego recorro sobre ella y hago un push_front de los elementos. El resultado debería ser cbaabc, que es exactamente lo que obtengo:

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;

Cuando utilizo iteradores inversos (bucle de rbegin() a rend() ) y uso push_back, esperaría un comportamiento similar, es decir, un resultado de abccba. Sin embargo, obtengo un resultado diferente:

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;

El resultado no es abccba , sino abcccba . Así es que hay una c adicional añadida.

Parece que el primer push_back también cambia el valor del iterador que se inicializó con rbegin (). Después de push_back, ya no apunta al tercer elemento de la lista (que anteriormente era el último), sino al cuarto elemento (que ahora es el último).

Probé esto con Visual Studio 2010 y con GCC y ambos devuelven el mismo resultado.

¿Es esto un error? ¿O algún comportamiento extraño de los iteradores inversos que no conozco?

Answer 1

Creo que para entender esto, es mejor comenzar por volver a emitir el bucle for como un bucle 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;
}

Junto con eso, tenemos que entender cómo funciona un reverse_iterator en general. Específicamente, un reverse_iterator realmente apunta al elemento después del que obtienes cuando lo eliminas. end() produce un iterador justo después del final del contenedor, pero para cosas como matrices, no hay una forma definida de apuntar justo antes del comienzo de un contenedor. Lo que hace C ++, en cambio, es hacer que el iterador comience justo después del final y progrese al principio, pero cuando lo eliminas, obtienes el elemento justo antes de lo que realmente señala.

Eso significa que tu código realmente funciona así:

Después de eso, obtienes casi lo que esperas, presionando B y luego A, así que terminas con ABCCCBA.

Answer 2

El estándar dice que los iteradores y las referencias siguen siendo válidos durante una inserción. No dice nada sobre los iteradores inversos. :-)

El reverse_iterator devuelto por rbegin() internamente mantiene el valor de end() . Después de un push_back() este valor obviamente no será el mismo que era antes. No creo que la norma diga lo que debería ser. Las alternativas obvias incluyen el último elemento anterior de la lista, o que permanece al final si ese es un valor fijo (como un nodo centinela).

Detalles técnicos: el valor devuelto por rend() no puede apuntar antes de begin() , porque no es válido. Por lo tanto, se decidió que rend() debería contener el valor de begin() y que todos los demás iteradores inversos deberían desplazarse una posición más. El operator* compensa esto y accede al elemento correcto de todos modos.

El primer párrafo de 24.5.1 iteradores inversos dice:

La plantilla de clase reverse_iterator es un adaptador de iterador que itera desde el final de la secuencia definida por su iterador subyacente hasta el comienzo de esa secuencia. La relación fundamental entre un iterador inverso y su iterador correspondiente i es establecida por la identidad:
&*(reverse_iterator(i)) == &*(i - 1) .

Answer 3

Intenta usar un iterador para ambos. Tratar:

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

y revertir a través de --i