Puede terminar() ser una operación costosa para contenedores STL

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) { 
     //...; 
} 

Dado que pocas veces he visto este estilo en cualquier código, me gustaría saber si la llamada consecutiva de end() realmente agrega una sobrecarga de tiempo de ejecución notable para bucles grandes sobre contenedores stl o si los compiladores ya optimizan dichos casos.

Editar: Como muchos de los comentarios a muy buenos señaló: Esta pregunta sólo es válida si el código dentro del bucle no no modifica el iterador final. De lo contrario, por supuesto, la llamada repetida de finalización es obligatoria.

Answer 1

El estándar C++ 11 (§ 23.2.1) establece que end tiene O (1) complejidad, 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 puede probar que el valor de retorno de end nunca cambiará luego tirando end fuera del circuito podría ser más rápido por alguna cantidad constante (como comentarios Steve Jessop, hay un montón de variables que pueden influencia si esto es cierto o no).

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

Answer 2

Depende de la implementación, pero no creo que end() ofrezca una gran demora en el rendimiento.

Answer 3

Si planea modificar la colección mientras itera, debe hacerlo de la 2da manera (el extremo puede cambiar); de lo contrario, la primera es teóricamente una fracción más rápida. Sin embargo, dudo que sea notable.

Answer 4

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

La complejidad de end es constante. Consulte la tabla 96 en N3337 en 23.2.1.

El uso de algoritmos de biblioteca estándar elude todo el dilema.

Answer 5

De hecho, el método end() está en línea. El segundo no lo llame cada vez, no creo que end() otorgue ningún retraso en el rendimiento.

Answer 6

std :: vector.end() (for example) devuelve un iterador por valor. En el segundo ciclo, crea un objeto en cada ciclo. 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 tu código será más legible. Tenga en cuenta que los dos bucles son equivalentes solo si no modifica la colección.

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

Answer 7

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

No estaba seguro de si esta respuesta califica como 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 ciertamente habría encontrado esta respuesta útil hace unos años. Por lo tanto, esta respuesta está dirigida al lector que simplemente quiere saber mejor forma de iterar a través de todos los elementos en un contenedor STL (vector, list, deque, etc.)).

Suponiendo que el PO quería tener acceso a cada elemento en el contenedor, que puede eludir fácilmente toda la cuestión de si la definición end es lo suficientemente rápido que llamar Container::end() escribiendo un range-based for loop:

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 PO ha pedido si la compensación entre la brevedad de simplemente comparar it a Container::end() en cada iteración y el rendimiento de declarar una variable end y compararla en cada paso vale la pena. Dado que los bucles for basados ​​en rangos proporcionan una alternativa simple, fácil de escribir y fácil de leer que también ocurre, internamente, declarar un iterador end en lugar de llamar al método Container::end() en cada paso, el número de casos en los que necesitamos detenernos en este la pregunta se ha reducido a un número limitado de casos.

Según cppreference.com, el bucle for-basada gama producirá código con los mismos efectos secundarios como los siguientes:

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