Iteración hacia atrás

Question

Supongamos que tengo un vector<int> myvec y quiero recorrer todos los elementos en orden inverso. Puedo pensar en algunas maneras de hacer esto:

for (vector<int>::iterator it = myvec.end() - 1; it >= myvec.begin(); --it) 
{ 
    // do stuff here 
} 

for (vector<int>::reverse_iterator rit = myvec.rbegin(); rit != myvec.rend(); ++rit) 
{ 
    // do stuff here 
} 

for (int i = myvec.size() - 1; i >= 0; --i) 
{ 
    // do stuff here 
} 

Entonces mi pregunta es ¿cuándo debo usar cada uno? ¿Hay una diferencia? Sé que el primero es peligroso porque si paso un vector vacío, entonces myvec.end() - 1 no está definido, pero ¿hay algún otro peligro o ineficiencia con esto?

Answer 1

La versión reverse_iterator muestra la intención y funciona en todos los contenedores, independientemente de su contenido.

La primera tiene la deficiencia que usted describe. También usa >=, que no funcionará para los iteradores de acceso no aleatorio.

El tercero tiene el problema de que i es un int. No podrá contener tanto como size() podría devolver. Hacerlo sin firmar funciona (vector<int>::size_type), pero luego tenemos el mismo problema que la solución uno. (0U - 1 ->Funky terminating checks ->:|)

Answer 2

Utilice siempre el segundo. El primero que descartó usted mismo, y el tercero no funciona para listas y tal.

Answer 3

Personalmente, me gustaría ir con la segunda.

Como indica el primero, es necesario que ajuste el ciclo en if (!myvec.empty()) para evitar un comportamiento indefinido.

Por último, es probable que debe utilizar un vector<int>::size_type o size_t, en cuyo caso el >= 0 está mal, lo que tendría que hacer != (size_t)-1 o similar.

La versión reverse_iterator es, por lo tanto, más limpia.

Answer 4

En cuanto a la primera versión, también terminará inevitablemente decrementando el iterador begin() al final de un ciclo (comportamiento indefinido).

La reverse_iterator está hecha para esto.

La tercera podría funcionar un poco mejor si se ha utilizado el algo más controvertida forma:

for (size_t i = vec.size(); i --> 0;) 

Esto podría ser un modismo si la gente dejara de resistirse. Utiliza un tipo de contador adecuado (sin signo) y contiene mnemónicos para memorizar y reconocer fácilmente.

Answer 5

Generalmente ninguno de los anteriores. En su lugar, normalmente debe sentarse y relajarse durante unos segundos, descubrir qué algoritmo desea aplicar y olvidarse de escribir un bucle. Lo más probable es que use reverse_iterator con él, pero dependiendo de lo que intente lograr, ese no siempre será el caso (por ejemplo, consulte std::copy_backwards).

Answer 6

Hay una cuarta opción (no necesariamente una buena opción, pero existe).Puede usar iteradores de acceso bidireccional/al azar de una forma que imita la forma iteradores inversa se implementan para evitar el problema con myvec.end()-1 en un iterador vacío:

for (vector<int>::iterator it = myvec.end(); it != myvec.begin(); --it) 
{ 
    // convert the loop controlling iterator to something that points 
    // to the item we're really referring to 

    vector<int>::iterator true_it = it; 
    --true_it; 


    // do stuff here 
    // but always dereference `true_it` instead of `it` 
    // this is essentially similar to the way a reverse_iterator 
    // generally works 

    int& x = *true_it; 
} 

o incluso:

for (vector<int>::iterator it = myvec.end(); it != myvec.begin();) 
{ 
    // decrement `it` before the loop executes rather than after 
    // it's a bit non-idiomatic, but works 
    --it; 

    int& x = *it; 

    // do stuff... 
} 

Como dije, esto no es necesariamente una buena opción (creo que Jerry Coffin's answer es el enfoque que debería tener primero), pero creo que es interesante ya que muestra cómo los iteradores inversos funcionan detrás de escena, y evita tener que convertir un reverse_iterator en un iterador para esos momentos en los que es posible que desee utilizar el iterador con algo que no aceptará un reverse_iterator (la conversión de reverse_iterator s a iterator s siempre parece dolerme la cabeza, por lo que a menudo evitaré reverse_iterators para evitar dolores de cabeza). Por ejemplo, si desea llamar inserción() para la ubicación de un iterador inverso se refiere a:

// if `it` is a reverse iterator, a call to insert might have to look something like: 

myvec.insert(--(it.base()), 42); // assume that you know the current vector capacity 
            // will avoid a reallocation, so the loop's 
            // iterators won't be invalidated 

// if `it` is a normal iterator... 

myvec.insert(it, 42);