C++ STL: ¿Qué método de iteración sobre un contenedor STL es mejor?

Question

Esto puede parecer frívolo para algunos de ustedes, pero ¿cuál de los siguientes 2 métodos de iteración sobre un contenedor STL es mejor? ¿Por qué?

class Elem; 
typedef vector<Elem> ElemVec; 
ElemVec elemVec; 

// Method 0 
for (ElemVec::iterator i = elemVec.begin(); i != elemVec.end(); ++i) 
{ 
    Elem& e = *i; 
    // Do something 
} 

// Method 1 
for (int i = 0; i < elemVec.size(); ++i) 
{ 
    Elem& e = elemVec.at(i); 
    // Do something 
} 

El método 0 parece más limpio STL, pero el Método 1 logra lo mismo con un código menor. La iteración simple sobre un contenedor es lo que aparece all sobre el lugar en cualquier código fuente. Por lo tanto, me inclino por elegir el Método 1, que parece reducir el desorden visual y el tamaño del código.

PD: Sé que los iteradores pueden hacer mucho más que un simple índice. Pero, por favor, mantenga la respuesta/discusión centrada en la iteración simple sobre un contenedor como se muestra arriba.

Answer 1

La primera versión funciona con cualquier contenedor y, por lo tanto, es más útil en funciones de plantilla que toman cualquier contenedor como un parámetro. También es concebiblemente un poco más eficiente, incluso para vectores.

La segunda versión solo funciona para vectores y otros contenedores de índice entero. Sería algo más idiomático para esos contenedores, será fácil de entender para los recién llegados a C++, y es útil si necesitas hacer algo más con el índice, que no es poco común.

Como siempre, no hay una respuesta simple de "este es mejor", me temo.

Answer 2

algunas ventajas más de método 0:

• si se muda de vector a otro contenedor del bucle sigue siendo el mismo,
• fácil de mover de iterador para const_iterator si es necesario,
• cuando C++ 0x arive, la tipificación automática de reducirá parte del desorden del código.

La principal desventaja es que en muchos casos escanea dos contenedores, en cuyo caso un índice es más limpio que mantener dos iteradores.

Answer 3

Si no te importa una (muy?) Pequeña pérdida de eficiencia, le recomiendo usar Boost.Foreach

BOOST_FOREACH(Elem& e, elemVec) 
{ 
    // Your code 
} 

Answer 4

Método 0 es más rápido y por lo tanto se recomienda.

El método 1 usa el tamaño() que se permite que sea O (1), dependiendo del contenedor y la implementación stl.

Answer 5

Depende del tipo de contenedor. Para un vector, probablemente no importe cuál use. El Método 0 se ha vuelto más idiomático, pero no es una gran diferencia, como todos dicen.

Si ha decidido utilizar un list, en cambio, el método 1 sería, en principio, ser O(N), pero en realidad no hay una lista at() método, por lo que ni siquiera se puede hacerlo de esa manera. (Así que en algún nivel su pregunta apila el mazo.)

Pero eso en sí mismo es otro argumento para el método 0: usa la misma sintaxis para diferentes contenedores.

Answer 6

Casualmente hice una prueba de velocidad recientemente (llenando 10 * 1024 * 1024 ints con rand()).
Estos son 3 carreras, el tiempo en nanosegundos

vect[i] time  : 373611869 
vec.at(i) time : 473297793 
*it = time  : 446818590 
arr[i] time  : 390357294 
*ptr time   : 356895778 

ACTUALIZACIÓN: se ha añadido STL-algoritmo de std :: generar, lo que parece correr más rápido, debido a la optimización de iterador-especial (VC++ 2008). tiempo en microsegundos.

vect[i] time  : 393951 
vec.at(i) time : 551387 
*it = time  : 596080 
generate = time : 346591 
arr[i] time  : 375432 
*ptr time   : 334612 

Conclusión: ¡Utilice algoritmos estándar, podrían ser más rápidos que un bucle explícito! (y también buenas prácticas)

Actualización: los tiempos anteriores estaban en una situación de E/S, hice las mismas pruebas con un CPU (iterar sobre un vector relativamente corto, que debería caber en la memoria caché repetidamente, multiplicar cada elemento por 2 y escribir de nuevo a vector)

//Visual Studio 2008 Express Edition 
vect[i] time  : 1356811 
vec.at(i) time : 7760148 
*it = time  : 4913112 
for_each = time : 455713 
arr[i] time  : 446280 
*ptr time   : 429595 

//GCC 
vect[i] time  : 431039 
vec.at(i) time : 2421283 
*it = time  : 381400 
for_each = time : 380972 
arr[i] time  : 363563 
*ptr time   : 365971 

Curiosamente iteradores y operador [] es considerablemente más lento en VC++ en comparación con for_each (que parece degradar los iteradores a punteros a través de algún plantilla-mágica para el rendimiento).
En GCC, los tiempos de acceso son peores para at(), lo cual es normal, porque es la única función de comprobación de rango de las pruebas.

Answer 7

Método 0, por varias razones.

• Se expresa mejor su intención, que ayuda a las optimizaciones del compilador, así como la legibilidad
• off-by-one errores son menos propensos
• que funciona incluso si se reemplaza el vector con una lista, que doesn' t tiene operador []

Por supuesto, la mejor solución a menudo será la solución 2: uno de los algoritmos estándar. std :: for_each, std :: transform, std :: copy o cualquier otra cosa que necesite. Esto tiene algunas ventajas adicionales:

• Expresa su intención aún mejor, y permite que algunas optimizaciones del compilador significativas (seguro SCL de MS realiza la comprobación de límites en sus métodos de 0 y 1, pero lo saltará en algoritmos std)
• Es menos código (en el sitio de llamada, al menos. Por supuesto, debe escribir un nombre de usuario o algo para reemplazar el cuerpo del bucle, pero en el sitio de uso, el código se limpia bastante, que es probablemente donde más importa

En general, evite sobreespecificar su código. Especifique exactamente lo que quiere que se haga, y nada más. Los gorithms suelen ser el camino a seguir, pero incluso sin ellos, si no necesitas el índice i, ¿por qué lo tienes? Use iteradores en su lugar, en ese caso.

Answer 8

El siguiente método de iteración sobre un contenedor de biblioteca estándar es el mejor.

Uso c++11 (y más allá) 's range-based for-loop con el auto specifier:

// Method 2 
for (auto& e: elemVec) 
{ 
    // Do something with e... 
} 

Esto es similar a su Method 0 pero requiere menos escribir, menos maintenence y funciona con cualquier contenedor compatible con std::begin() y std::end(), incluidos matrices antiguas.

Answer 9

Una posibilidad no se considera por encima de: dependiendo de los detalles de "hacer algo", uno puede tener método y el método 0 1 simultáneamente, usted no tiene que elegir:

for (auto i = elemVec.begin(), ii = 0; ii < elemVec.size(); ++i, ++ii) 
{ 
    // Do something with either the iterator i or the index ii 
} 

De esta manera, la búsqueda de la el índice o el acceso al miembro correspondiente se obtienen con una complejidad trivial.