c++ - metodo - ordenamiento burbuja python

Complejidad temporal del operador delete

Question

Esta pregunta ya tiene una respuesta aquí:

• Es Big-O de la sentencia C ++ ''delete [] Q;'' O (1) o O (n)? 2 respuestas

¿Cuál es la complejidad de tiempo del operador delete[] ?

Me refiero a cómo se implementa: ¿itera sobre todos los elementos de la matriz y llama a destructor para cada elemento?

¿Este operador hace lo mismo con los tipos primitivos ( int , etc.) y los tipos definidos por el usuario?

Answer 1

¿Cuál es la complejidad de tiempo del operador delete[] ?

La cantidad de tiempo requerido es, por supuesto, la implementación definida. Sin embargo, el operador solo se aplica al puntero a la matriz 1D y, por lo tanto, es O (1).

Me refiero a cómo se implementa: ¿itera sobre todos los elementos de la matriz y llama a destructor para cada elemento?

Sí.
Siempre que se llame solo en el puntero exacto al que se asigna una memoria creada con el new[] . Para los tipos primitivos no hay destructores definidos por el usuario.

¿Este operador hace lo mismo con los tipos primitivos (int, etc.) y los tipos definidos por el usuario?

La comparación no es justa, porque los tipos primitivos no tienen un destructor definido por el usuario y no pueden ser polimórficos.
Por ejemplo, delete[] en una clase polimórfica es un comportamiento indefinido . es decir

Base* p1 = new Derived, *p2 = new Derived[2];
delete p1; // ok
delete[] p2; // bad

Answer 2

La implementación de delete y delete[] se compone de dos fases:

1. llamada recursiva a los destructores (si los hay)
2. desasignación de memoria para objeto eliminado

Por no hablar de la cadena de llamadas a los destructores, cuya complejidad se rige esencialmente por usted, nos quedamos con la forma en que se libera la memoria para considerarla.

El segundo punto no está cubierto por la especificación de C ++. Por lo tanto, cualquier compilador / OS de compilación es libre de adoptar su propia estrategia.

Una estrategia de asignación / desasignación de memoria común es asignar una página de memoria completa cuando es necesario desde el sistema operativo, luego en cada new / new[] , devolver una porción del tamaño apropiado, cuya longitud y atributos se almacenan dentro de la página como un encabezado / pie de página. Una delete / delete[] puede ser tan simple como marcar el mismo fragmento como "libre", que es claramente O (1).

Si la complejidad de la desasignación de memoria es O (1), entonces la complejidad de una delete se rige esencialmente por las llamadas a los destructores . La implementación predeterminada no hace (casi) nada, y es un O (1) para una sola llamada, por lo tanto un O (n) general , donde n es el número total de llamadas (por ejemplo, si el objeto que se destruye tiene dos campos cuyo destructor es llamado, luego n = 1 (object) + 2 (o. fields) = 3 ).

Poniendo todas las piezas juntas: puede incrementar la complejidad de manera arbitraria realizando operaciones en el destructor (que usted puede escribir), pero no puede "rendir mejor" ¹ que O (n) (n definido en el párrafo anterior). La forma oficialmente correcta de afirmar esto es: "la complejidad de la delete es un Omega (n)" .

¹ Permíteme ser un poco informal en este punto.

Answer 3

Para los tipos de clase, la complejidad teórica es O(n) . Se llama al destructor para cada elemento. Por supuesto, depende de la implementación cumplir con el comportamiento observable, por lo que si el destructor es un no-op o el comportamiento es el mismo que con solo marcar todo el fragmento como liberado, la complejidad podría ser solo O(1) .

Para los tipos primitivos, es probable que el compilador simplemente libere todo el trozo de memoria a la vez, por lo tanto la complejidad O(1) .

Answer 4

::operator delete[] se documenta en cplusplus.com (que a veces es mal visto) como:

operator delete[] se puede llamar explícitamente como una función regular, pero en C ++, delete[] es un operador con un comportamiento muy específico : una expresión con el operador delete[] , primero llama a los destructores apropiados para cada elemento de la matriz ( si estos son de un tipo de clase), y luego llama al operator delete[] función operator delete[] (es decir, esta función) para liberar el almacenamiento.

de modo que se llama al destructor n veces (una vez para cada elemento), y luego se llama una vez a la "función" de liberación de memoria.

^{Observe que cada destrucción puede tomar un tiempo diferente (o incluso una complejidad) que los otros. En general, la mayoría de las destrucciones son rápidas y tienen la misma complejidad ... Pero ese no será el caso si cada elemento destruido es un árbol o nodo complejo o gráfico ...}

Para tipos primitivos como int el destructor ficticio de int es un no-op. El compilador probablemente optimizaría eso (si se le pide).

Debe verificar el estándar C++11 real, o al menos su n3337 trabajo final n3337 , que dice (gracias a Matteo Italia por señalarlo en un comentario) en §5.3.5.6 página 110 de n3337:

Si el valor del operando de la expresión de eliminación no es un valor de puntero nulo, la expresión de eliminación invocará el destructor (si existe) para el objeto o los elementos de la matriz que se eliminará. En el caso de una matriz, los elementos se destruirán en orden decreciente de direcciones (es decir, en orden inverso a la finalización de su constructor; ver 12.6.2)

Si usa (y confía lo suficiente) en GCC 4.8 o superior, podría haber usado el compilador g++ con la -fdump-tree-phiopt o -fdump-tree-all (tenga cuidado, ¡están descargando muchos archivos!), O el complemento MELT , para consultar la representación intermedia de Gimple de algún ejemplo. O use -S -fverbose-asm para obtener el código del ensamblador. Y también desea agregar indicadores de optimización como -O1 o -O2 ...

^{NB: En mi humilde opinión, cppreference.com también es un sitio interesante sobre C ++, vea acerca de delete (como lo comentó Cubbi )}