c++ - resueltos - ¿Es costoso devolver una lista estándar::?

estadistica elemental solucionario

Question

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

Answer 1

Creo, se llama el constructor de copia.

Answer 2

Depende (como siempre). El constructor de copia puede o no ser invocado por devolución en el siguiente código.

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

No se puede invocar si el compilador aplica la optimización del valor de retorno . Si se llama al constructor de copia, es probable que sea más caro en comparació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 directa. Entonces, solo cuando mi generador de perfiles dice que esto es un problema, considero las optimizaciones.

Answer 3

Podría escribir su propio constructor de copia para que no se copie.

Answer 4

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

Answer 5

Si devuelve por valor, se llamará al constructor de copia y los elementos se copiarán uno por uno. En ocasiones, la optimización de valores nombrados lo salvará, como lo señaló Onebyone.

Sus principales opciones para garantizar que la copia no tendrá lugar son:

• Pase una lista por referencia para que la función la complete. De esta manera, le dirá a la función dónde colocar los datos y no será necesario hacer una copia porque la colocó en su lugar final.
• Asigne una lista en el montón y devuélvala. Debes devolverlo en un puntero inteligente como std :: auto_ptr o boost :: shared_ptr para asegurarte de que se elimine y sea seguro de excepción.

Answer 6

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

Si la lista está incorporada en la función que la está devolviendo, entonces podría beneficiarse de la optimización del valor de retorno nombrado, para evitar una copia innecesaria. Aunque eso es específico de tu compilador. Nunca se aplica si, por ejemplo, la lista ya existía antes de llamar a la función (por ejemplo, si es una variable miembro de un objeto).

Un lenguaje 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;
}

Tú lo haces:

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

Entonces la persona que llama hace:

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

A menudo, una vez que el compilador ha terminado de alinearse y optimizarse, el código es más o menos idéntico.

La ventaja de esto es que la persona que llama no está vinculada a una colección en particular; por ejemplo, puede agregar los elementos a un vector en lugar de a una lista, si eso es más útil para las circunstancias particulares. Si solo necesita ver cada elemento una vez, en lugar de todos juntos, entonces puede ahorrar memoria procesándolos en modo de transmisión usando 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 la persona que llama en el momento de la compilación, y puede terminar con un montón de 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 IntVisitor, con un miembro virtual puro función, y que la persona que llama proporcione una instancia de ella.

[Editar: TED señala en un comentario que otra forma de evitar la copia sin usar plantillas es que la persona que llama pase una lista por referencia. Esto ciertamente funciona, solo le da a la persona que llama menos flexibilidad que la plantilla, y por lo tanto no es el lenguaje utilizado por el STL. Es una buena opción si no desea la "ventaja de esto" que describo anteriormente. Sin embargo, una de las intenciones originales detrás de la STL es separar los "algoritmos" (en este caso, lo que determine los valores) de los "contenedores" (en este caso, el hecho de que los valores se almacenen en una lista, como opuestos). a un vector o una matriz o un conjunto de auto-clasificación, o simplemente imprimido sin almacenarlos en absoluto).]