En un libro de programación C++ vi lo siguiente para un iterador std::list:No está llamando `list <T> :: end()` inefficient?
for (iterator = list.start(); iterator != list.end(); iterator++)
No es ineficaz para llamar list.end() todo el tiempo? ¿Sería mejor guardar el final en otra variable o el compilador de C++ (es decir, g ++) se ocuparía de esto automáticamente?
Es poco probable que la llamada al std::list<T>::end() sea un gran problema de eficiencia y probablemente solo lea un valor único. Sin embargo, le daría al compilador una pista de que no debe cambiar al almacenarla como variable. Para otros contenedores, un cómputo puede estar involucrado además de leer una dirección base que es un poco más complicada. Todavía no hay nada espectacular, pero posiblemente valga la pena evitarlo.
Tenga en cuenta, sin embargo, que también puede cambiar la semántica del bucle: si el cuerpo del bucle puede agregar elementos, el anterior puede moverse. Curiosamente, no encuentro ningún requisito específico en la norma que indique si el std::list<T>::end() puede cambiar al insertar elementos en el contenedor (puedo imaginar implementaciones en las que cambia así como en otras donde no, pero lo más probable es que no cambie). , aunque). Si desea obtener un comportamiento garantizado cuando también modifica la lista, puede llamar al list.end() en cada iteración.
Por cierto, hay una mayor preocupación de rendimiento que tendría sobre el uso de iterator++ en lugar de ++iterator, especialmente esto es lo que el autor utilizó en el libro. Aún así, se trata de una micro optimización, como almacenar el resultado de list.end(), pero es una tarea barata.
"No encuentro ningún requisito específico en la norma que indique si' std :: list
¿Qué impide que la implementación tenga 'end()' apuntando a un objeto medio cocido que se inicializa con el nuevo valor al insertar un elemento al final? El iterador permanece válido pero ya no apunta al final y no había ningún objeto en esta ubicación antes, por lo que ninguna referencia o puntero deja de ser válido. Da la casualidad que así es como 'std :: vector
Punto justo. Fuera de interés, si tengo un iterador que * no es * un iterador final, y lo inserto antes, ¿qué dice que después no apunta al objeto recién insertado? Incluso con suficiente capacidad, 'vector :: insert' invalida iteradores y referencias después del punto de inserción, por lo que el no requisito para que el antiguo iterador final siga siendo un iterador final es obvio allí. –
list::end() debe tener complejidad de tiempo constante y para las listas vinculadas en particular, significa que es probablemente muy eficiente.
Podría ser un poco más eficiente almacenar el valor si su algoritmo lo permite (de nuevo, la diferencia es poco probable que sea grande para listas especialmente vinculadas).
¡Ah, y lea la respuesta de Steve Jessop sobre probar la eficiencia usted mismo!
http://www.cplusplus.com/reference/stl/list/end/ - Reviso cosas allí, vea "Complejidad". – Shi
@Shi, tenga en cuenta que la complejidad "constante" no significa una ausencia de operación. Los vectores en particular probablemente complementan el puntero dentro de su respectivo 'end()'; las listas probablemente no lo hagan (como mencioné) –
La complejidad constante aún lleva tiempo, y dependiendo de su STL, implementación, contenedor elegido, etc. (especialmente contenedores que no sean STL), puede ser una cantidad de tiempo significativa. – ssube
En la práctica, para contenedores STL, container::end() es extremadamente económico. De hecho, el estándar de C++ exige complejidad algorítmica para varios métodos de varias clases (si no para todos), y container::end() es siempre de tiempo constante.
Además, el compilador es libre de alinear esos métodos, eliminando esencialmente cualquier sobrecarga que pueda tener. No puedo pensar en otra manera de obtener el final de una lista en tiempo constante que almacenarla, por lo que su llamada list.end() probablemente termine siendo un acceso de campo, que no es más costoso en plataformas x86 que almacenarlo en la pila.
Su millaje puede variar con otras colecciones, pero es una apuesta segura que list.end() no terminará siendo su cuello de botella.
Es poco probable que haga una diferencia.
Las funciones de contenedor estándar se incorporan, por lo que no debe haber una sobrecarga de llamadas de función notable. Lo que queda es si el optimizador es lo suficientemente inteligente como para evitar una sobrecarga innecesaria que no es estrictamente necesaria para realizar la comparación. Por ejemplo: ¿realmente crea un objeto temporal list::iterator, completa su campo de posición actual y luego vuelve a leer ese campo, o la comparación termina como una comparación de puntero entre un valor de iterator y un valor en el encabezado del ¿lista?
Incluso si hay una sobrecarga innecesaria, puede ser insignificante en comparación con el incremento del iterador, y aún más insignificante en comparación con su cuerpo de bucle.
Puede probarlo, que es más confiable que adivinar. Recuerde habilitar la optimización: probar el rendimiento sin optimización es como decir que Blake debe ser más rápido que Bolt si Blake camina más rápido desde la pista de calentamiento al autobús.
En general, no, no es ineficiente. end() normalmente será una función en línea, y el compilador generará un buen código para hacer lo que haga. Más al punto, ineficiente en comparación con qué? Sí, podría agregar código para crear una variable que contenga el resultado, y eso podría o no ser un poco más rápido que simplemente llamar al end(). Parece muy poco probable que un cambio de este tipo suponga una diferencia de velocidad lo suficientemente grande como para convertir un programa demasiado lento en uno que cumpla con los requisitos.
Si necesita micro-optimizar, sí.
En general, llamar al list.end() no tendrá una penalización de rendimiento significativa y probablemente no constituirá un problema. Puede devolver el mismo valor en cada llamada, puede estar en línea, y así sucesivamente. Si bien no es lento, lleva algo de tiempo.
Si necesita absolutamente la velocidad, quiere usar for (iterator = list.start(), end = list.end; iteration != end; ++iterator). Esto almacena en caché el iterador final (y realiza una preincrementación), y no debe tener llamadas repetidas.
El segundo tipo es generalmente innecesario, pero si .end() es costoso o el bucle es muy grande, puede ser útil.
Si bien la optimización prematura es mala, los buenos hábitos no lo son. Si no espera que su condición de terminación de bucle para cambiar, es decir, que no está cambiando el contenedor, a continuación, este patrón se puede utilizar:
for (mylist::iterator it = alist.begin(), finish = alist.end(); it != finish; ++it)
El compilador es poco probable que esta optimización para usted si puede' t determinar que el contenedor no está cambiando.
Tenga en cuenta que esto es poco probable que haga una diferencia de tiempo mensurable, pero no puede doler.
Si el código se está ejecutando en un sistema que es ajustado para registros o tiene una pila limitada, la creación de variables adicionales puede dañar. –
@PeteBecker, dado que la variable reemplaza el resultado de una llamada de función, creo que es probable que ayude en lugar de perjudicar. Aunque aún tengas razón, es imposible saberlo sin mirar el código generado. –
Excepto que el valor debe mantenerse alrededor del cuerpo del bucle; con una llamada de función, el resultado puede descartarse después de ser utilizado. –
Una buena razón para no almacenar en caché end() en std::list es que le impide hacer el siguiente error:
for (iterator = list.rstart(), end = list.rend(); iterator != end; iterator++) {
// modify list
No iteradores serán invalidados cuando realiza modificaciones en std::list, pero rend no es un centinela (apunta al primer elemento de la lista subyacente), lo que significa que dejará de ser el final de la lista si se agrega al final de la lista inversa (también anterior al comienzo de la lista no revertida)
' std :: list :: end' es el final de una lista enlazada con doble finalización, por lo que es debería ser una operación de tiempo constante. Dado que no se agrega mientras está en el bucle, un compilador de optimización debería poder almacenarlo en caché. – oldrinb
Esto sería en el ámbito de la "optimización prematura". Preocuparse demasiado pronto puede causar problemas, especialmente porque si agrega o elimina elementos a la lista dentro de su ciclo, el extremo puede cambiar. Si has aislado una parte específica de tu código (que se basa en esto) como un cerdo de CPU, entonces optimízate por todos los medios, pero de lo contrario hay peces más grandes en el mar. – Wug
@Wug Si sabe que '.end()' es un tiempo constante, sí (y sí, sé que debe estar en C++, para este contenedor específico). Pero para las listas que pueden ser muy largas y cuyo '.end()' es O (n), dicha optimización no es prematura en absoluto. – delnan