¿Es costoso devolver una lista estándar?

Question

Me preguntaba si devolver una lista, en lugar de devolver un puntero a uno, era costoso en términos de rendimiento porque, si no recuerdo mal, una lista no tiene muchos atributos (¿no es algo así como 3 punteros? para la posición actual, una para el comienzo y otra para el final?).

Answer 1

Si devuelve un valor de std::list, no solo copiará el encabezado de la lista, sino que copiará un nodo de la lista por cada elemento de la lista. Entonces sí, para una lista grande es costoso.

Si la lista está integrada en la función que la está devolviendo, entonces es posible que pueda beneficiarse de la optimización del valor de retorno denominado para evitar una copia innecesaria. Eso es específico de tu compilador, sin embargo. Nunca se aplica si, por ejemplo, la lista ya existía antes de llamar a la función (por ejemplo, si se trata de una variable miembro de un objeto).

Una expresión común en C++, para evitar devolver contenedores por valor, es tomar un iterador de salida como parámetro. Así que en lugar de:

std::list<int> getListOfInts() { 
    std::list<int> l; 
    for (int i = 0; i < 10; ++i) { 
     l.push_back(i); 
    } 
    return l; 
} 

lo hace:

template<typename OutputIterator> 
void getInts(OutputIterator out) { 
    for (int i = 0; i < 10; ++i) { 
     *(out++) = i; 
    } 
} 

Entonces la persona que llama:

std::list<int> l; 
getInts(std::back_inserter(l)); 

A menudo, una vez que el compilador ha terminado de procesos en línea y la optimización, el código es más o menos idéntico .

La ventaja de esto es que la persona que llama no está atada a una colección en particular; por ejemplo, puede agregar los elementos a un vector en lugar de una lista si es más útil para las circunstancias particulares. Si solo necesita ver cada elemento una vez, en lugar de todos juntos, puede guardar la memoria procesándola en modo de transmisión mediante un iterador de salida de su propio diseño.

Las desventajas son las mismas que con cualquier código de plantilla: la implementación debe estar disponible para el llamante en tiempo de compilación y puede terminar con un gran código de objeto "duplicado" para múltiples instancias de la plantilla. Por supuesto, puede usar el mismo patrón sin usar plantillas, tomando un puntero de función (más un puntero de datos de usuario si lo desea) como parámetro y llamándolo una vez con cada elemento, o definiendo una clase abstracta de IntVisitor, con un miembro virtual puro función, y que la persona que llama proporcione una instancia de la misma.

[Editar: T.E.D señala en un comentario que otra forma de evitar la copia sin utilizar plantillas es que la persona que llama pase en una lista por referencia. Esto ciertamente funciona, solo le da a quien llama menos flexibilidad que la plantilla, y por lo tanto no es la expresión idiomática utilizada por el STL. Es una buena opción si no quieres la "ventaja de esto" que describo arriba. Sin embargo, una de las intenciones originales detrás del STL es separar "algoritmos" (en este caso lo que determina los valores) de "contenedores" (en este caso, el hecho de que los valores se almacenan en una lista, en lugar de a un vector o una matriz o un conjunto de auto clasificación, o simplemente impreso sin guardarlos en absoluto).]

Answer 2

Creo que se llama al constructor de copias.

Answer 3

Puede ser costoso, ya que copiará todos los elementos de la lista. Más importante aún, tiene un comportamiento diferente: ¿quieres una copia de la lista o quieres un puntero a la lista original?

Answer 4

Si devuelve el valor, se llamará al constructor de copia y los elementos se copiarán uno por uno. A veces será salvado por la optimización del valor con nombre como onebyone señalado.

Sus principales opciones para asegurarse de que la copia no se llevará a cabo son:

• Pass en una lista por referencia a cumplimentar por la función. De esta forma, le dirá a la función dónde colocar los datos y no será necesario hacer ninguna copia porque la puso en su lugar final.
• Asigne una lista en el montón y devuelvala. Debe devolverlo en un puntero inteligente como std :: auto_ptr o boost :: shared_ptr para asegurarse de que se elimine y de que sea excepcionalmente seguro.

Answer 5

Depende (como siempre). El constructor de copia puede invocarse o no por retorno en el siguiente código.

std::list<int> foo() { 
    std::list<int> bar; 
    // ... 
    return bar; 
}; 

Es no podrá invocarse si el compilador se aplica return value optimization. Si se llama al constructor de copias, entonces es probablemente más costoso en relación con un puntero para listas más grandes, y si no se llama, entonces es más rápido devolver la lista directa (porque evita una asignación dinámica)

Personalmente, no me preocupo por eso y devuelvo la lista correcta. Entonces, solo cuando mi generador de perfiles dice que este es un problema, considero las optimizaciones.