c++ - Puede terminar() ser una operación costosa para contenedores stl

performance containers

Question

En https://doc-snapshots.qt.io/qtcreator-extending/coding-style.html se recomienda escribir para bucles como los siguientes:

Container::iterator end = large.end();
for (Container::iterator it = large.begin(); it != end; ++it) {
//...;
}

en lugar de

for (Container::iterator it = large.begin(); it != large.end(); ++it) {
//...;
}

Como rara vez he visto este estilo en ningún código, me gustaría saber si la llamada consecutiva de end () realmente agrega una sobrecarga notable en el tiempo de ejecución de los bucles grandes sobre los contenedores stl o si los compiladores ya optimizan estos casos.

Edición: como muchos de los buenos comentarios señalaron: esta pregunta solo es válida si el código dentro del bucle no modifica el iterador final . De lo contrario, por supuesto, la repetida llamada de finalización es obligatoria.

Answer 1

De hecho, el método end () está en línea. El segundo no lo llama cada vez, no creo que end () genere un retraso en el rendimiento.

Answer 2

Depende de la implementación, pero no creo que end() dé tanto retraso en el rendimiento.

Answer 3

El estándar C ++ 11 (§ 23.2.1) ordena que el end tenga una complejidad O (1), por lo que una implementación conforme tendría las mismas características de rendimiento para ambas versiones.

Dicho esto, a menos que el compilador pueda probar que el valor de retorno del end nunca cambiará, el hecho de sacar el end del bucle podría ser más rápido en una cantidad constante (como comenta Steve Jessop, hay muchas variables que pueden influir en si esto es cierto o no). no).

Aún así, incluso si en un caso particular no hay absolutamente ninguna diferencia de rendimiento, sacar tales pruebas del bucle es un buen hábito. Un hábito aún mejor para entrar es utilizar algoritmos estándar como dice @pmr, lo que evita el problema por completo.

Answer 4

Esto tiene que ver con que el end sea ​​costoso y más sobre la capacidad de un compilador para ver que el end no cambiará a través de un efecto secundario en el cuerpo del bucle (que es un invariante del bucle).

La complejidad del end debe ser constante por el estándar. Ver tabla 96 en N3337 en 23.2.1 .

El uso de algoritmos de biblioteca estándar evita todo el dilema muy bien.

Answer 5

Para cualquiera que lea esto ahora, la pregunta se ha convertido en un punto discutible con C ++ 11.

No estaba seguro de si esta respuesta califica como una respuesta, porque en realidad no aborda el punto de la pregunta. Pero sí creo que es válido señalar que el problema planteado aquí rara vez se encontrará en la práctica para un programador de C ++ 11, y desde luego me habría parecido útil esta respuesta hace unos años. Por lo tanto, esta respuesta está dirigida al lector que simplemente quiere saber la mejor manera de iterar a través de todos los elementos en un contenedor STL ( vector , list , deque , etc.).

Suponiendo que el OP deseara el acceso a cada elemento en el contenedor, podemos eludir fácilmente la pregunta completa de si la definición de end es lo suficientemente más rápida que llamar a Container::end() escribiendo un bucle for basado en rango :

Container container; // my STL container that has been filled with stuff
// (note that you can replace Container::value_type with the value in the container)
// the standard way
for (Container::value_type element : container) {
// access each element by ''element'' rather than by ''*it''
}
// or, if Container::value_type is large
Container container; // fill it with something
for (Container::value_type& element : container) {
//
}
// if you''re lazy
Container container; // fill it with something
for (auto element : container) {
//
}

El OP ha preguntado si vale la pena el compromiso entre la brevedad de simplemente compararla con Container::end() en cada iteración y el rendimiento de declarar un end variable y comparar eso en cada paso. Dado que los bucles basados ​​en rango proporcionan una alternativa simple, fácil de escribir y fácil de leer que también sucede a nivel interno, declara un iterador end lugar de llamar al método Container::end() en cada paso, la cantidad de casos en los que La necesidad de detenerse en esta cuestión se ha reducido a un número limitado de casos.

Según cppreference.com , el bucle for basado en rango producirá código con los mismos efectos secundarios que los siguientes:

{
auto && __range = range_expression ;
for (auto __begin = begin_expr,
__end = end_expr;
__begin != __end; ++__begin) {
range_declaration = *__begin;
loop_statement
}
} 

Answer 6

Si planea modificar la colección a medida que itera, debe hacerlo de la segunda forma (el final puede cambiar); de lo contrario, la primera es teóricamente una fracción más rápida. Aunque dudo que sea notable.

Answer 7

std :: vector.end () (por ejemplo) devuelve un iterador por valor. En el segundo bucle creas un objeto en cada bucle. El estándar de codificación le indica que no cree un objeto si no lo necesita. El compilador puede ser inteligente y optimizar el código para usted, sin embargo esto no es garantía. Una solución mucho mejor es usar algoritmos stl. Ya están optimizados y su código será más legible. Tenga en cuenta que los dos bucles son equivalentes solo si no modificó la colección.

PS es muy probable que la diferencia en el rendimiento sea mínima.