Complexité temporelle de l'opérateur delete[]

Question

Quelle est la complexité temporelle de l'opérateur delete[] ?

Je veux dire comment est-il implémenté - itère-t-il sur tous les éléments du tableau et appelle-t-il le destructeur pour chaque élément ?

Cet opérateur fait-il la même chose pour les types primitifs (int, etc.) et les types définis par l'utilisateur ?

Answer 1

::operator delete[] est documenté sur cplusplus.com (ce qui est parfois mal vu) comme suit :

operator delete[] peut être appelé explicitement comme une fonction ordinaire, mais en C++, delete[] est un opérateur avec un comportement très spécifique : Une expression avec l'opérateur delete[], appelle d'abord les destructeurs appropriés de chaque élément du tableau (si ces éléments sont de type classe), puis appelle la fonction operator delete[] (c'est-à-dire cette fonction) pour libérer l'espace de stockage.

ainsi le destructeur est appelé n fois (une fois pour chaque élément), puis la "fonction" de libération de mémoire est appelée une fois.

Remarquez que chaque destruction peut prendre un temps différent (ou même une complexité différente) des autres. En général, la plupart des destructions sont rapides et ont la même complexité.... Mais cela ne sera pas le cas si chaque élément détruit est un arbre, un nœud ou un graphe complexe...

Pour les types primitifs comme int, le destructeur fictif de int est une opération nulle. Le compilateur optimiserait probablement cela (si demandé).

Vous devriez vérifier le vrai standard C++11, ou au moins son dernier brouillon de travail n3337, qui dit (merci à Matteo Italia pour l'avoir signalé dans un commentaire) à la page 110 de n3337 dans la section 5.3.5.6 :

Si la valeur de l'opérande de l'expression de suppression n'est pas une valeur de pointeur nulle, l'expression de suppression invoquera le destructeur (s'il y en a un) pour l'objet ou les éléments du tableau qui sont supprimés. Dans le cas d'un tableau, les éléments seront détruits dans l'ordre des adresses décroissantes (c'est-à-dire, dans l'ordre inverse de l'achèvement de leur constructeur, voir 12.6.2)

Si vous utilisez -et faites suffisamment confiance à- GCC 4.8 ou mieux, vous pourriez avoir utilisé le compilateur g++ avec l'option -fdump-tree-phiopt ou -fdump-tree-all (attention, ils génèrent beaucoup de fichiers!), ou le plugin MELT, pour interroger la représentation intermédiaire Gimple d'un exemple. Ou utilisez -S -fverbose-asm pour obtenir le code assembleur. Et vous voudrez également ajouter des drapeaux d'optimisation comme -O1 ou -O2....

NB: Selon moi, cppreference.com est aussi un site intéressant sur le C++, voir ici à propos de delete (comme commenté par Cubbi)

Answer 2

L'implémentation de delete et delete[] est composée de deux phases:

1. appel récursif aux destructeurs (le cas échéant)
2. désallocation de mémoire pour l'objet supprimé

Laissons de côté la chaîne d'appels aux destructeurs, dont la complexité est essentiellement gouvernée par vous, nous devons maintenant considérer comment la mémoire est libérée.

Le deuxième point n'est pas couvert par la spécification C++. Ainsi, toute suite de compilateurs/OS est libre d'adopter sa propre stratégie.

Une stratégie commune d'allocation/désallocation de mémoire est d'allouer une page mémoire entière lorsque cela est nécessaire à partir du système d'exploitation, puis à chaque new/new[], de retourner un morceau de la taille appropriée, dont la longueur et les attributs sont ensuite stockés à l'intérieur de la page en tant qu'en-tête/pied de page. Un delete/delete[] correspondant peut être aussi simple que de marquer le même morceau comme "libre", ce qui est clairement O(1).

Si la complexité de la désallocation mémoire est O(1), alors la complexité d'un delete est essentiellement gouvernée par les appels aux destructeurs. L'implémentation par défaut ne fait (presque) rien, et c'est un O(1) pour un seul appel, donc un total de O(n), où n est le nombre total d'appels (par exemple, si l'objet en cours de destruction a deux champs dont le destructeur est appelé, alors n = 1 (objet) + 2 (champs o.) = 3).

En regroupant tous les éléments: vous pouvez augmenter arbitrairement la complexité en effectuant des opérations dans le destructeur (que vous pouvez écrire), mais vous ne pouvez pas "faire mieux"¹ que O(n) (n étant défini dans le paragraphe précédent). La manière formellement correcte de déclarer ceci est: "la complexité de delete est un Oméga(n)".

---

¹ permettez-moi d'être un peu informel sur ce point

Answer 3

Pour les types de classe, la complexité théorique est O(n). Le destructeur est appelé pour chaque élément. Bien sûr, c'est à l'implémentation de respecter le comportement observable, donc si le destructeur ne fait rien ou si le comportement est le même qu'en marquant simplement tout le bloc comme libéré, la complexité pourrait être juste O(1).

Pour les types primitifs, le compilateur libérera probablement tout le bloc de mémoire en une seule fois, donc la complexité est O(1).

Answer 4

Quelle est la complexité temporelle de l'opérateur delete[] ?

La durée nécessaire est bien entendu définie par l'implémentation. Cependant, l'opérateur ne s'applique qu'au pointeur vers le tableau 1D et est donc en O(1).

Ce que je veux dire, c'est comment est-il implémenté - est-ce qu'il itère sur tous les éléments du tableau et appelle le destructeur pour chaque élément ?

Oui.
À condition qu'il soit appelé uniquement sur le exact pointeur qui a reçu une mémoire créée en utilisant new[]. Pour les types primitifs, il n'y a pas de destructeurs définis par l'utilisateur.

Cet opérateur fonctionne-t-il de la même manière pour les types primitifs (int, etc.) et les types définis par l'utilisateur ?

La comparaison n'est pas juste, car les types primitifs n'ont pas de destructeurs définis par l'utilisateur et ils ne peuvent pas être polymorphes.
Par exemple, delete[] sur une classe polymorphe est un comportement indéfini. c.-à-d.

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