La destruction d'une grande liste va-t-elle déborder ma pile?

Considérez l'implémentation de liste liée individuellement suivante:

struct node {
    std::unique_ptr<node> next;
    ComplicatedDestructorClass data;
}

Supposons maintenant que j'arrête d'utiliser une std::unique_ptr<node> headinstance qui sort alors du champ d'application, provoquant l'appel de son destructeur.

Est-ce que cela fera exploser ma pile de listes suffisamment grandes? Est-il juste de supposer que le compilateur fera une optimisation assez compliquée (le unique_ptrdestructeur en ligne dans nodele s, puis utilisera la récursivité de la queue), ce qui devient beaucoup plus difficile si je fais ce qui suit (puisque le datadestructeur masquerait nextle sien , le rendant difficile pour que le compilateur remarque la possibilité de réorganisation et d'appel de queue):

struct node {
    std::shared_ptr<node> next;
    ComplicatedDestructorClass data;
}

Si en dataquelque sorte a un pointeur vers son, nodeil peut même être impossible pour la récursivité de la queue (bien que nous devrions bien sûr nous efforcer d'éviter de telles violations de l'encapsulation).

En général, comment est-il censé détruire cette liste sinon? Nous ne pouvons pas parcourir la liste et supprimer le nœud "actuel" car le pointeur partagé n'en a pas release! Le seul moyen est avec un deleter personnalisé, qui me fait vraiment mal.

Oui, cela finira par faire exploser votre pile, à moins que le compilateur ne se trouve à appliquer une optimisation d'appel de queue au nodedestructeur et shared_ptr au destructeur de. Ce dernier est extrêmement dépendant de l'implémentation de bibliothèque standard. La STL de Microsoft, par exemple, ne le fera jamais, car shared_ptrelle diminue d'abord le nombre de références de sa pointe (peut-être en détruisant l'objet), puis diminue le nombre de références de son bloc de contrôle (le faible nombre de références). Le destructeur intérieur n'est donc pas un appel de queue. Il s'agit également d'un appel virtuel , ce qui rend encore moins probable son optimisation.

Les listes typiques contournent ce problème en n'ayant pas un nœud propre au suivant, mais en ayant un conteneur qui possède tous les nœuds et utilise une boucle pour supprimer tout dans le destructeur.

Réponse tardive mais puisque personne ne l'a fournie ... J'ai rencontré le même problème et l'ai résolu en utilisant un destructeur personnalisé:

virtual ~node () throw () {
    while (next) {
        next = std::move(next->next);
    }
}

Si vous avez vraiment une liste , c'est-à-dire que chaque nœud est précédé d'un nœud et a au plus un suiveur, et que vous êtes listun pointeur sur le premier node, ce qui précède devrait fonctionner.

Si vous avez une structure floue (par exemple un graphique acyclique), vous pouvez utiliser ce qui suit:

virtual ~node () throw () {
    while (next && next.use_count() < 2) {
        next = std::move(next->next);
    }
}

L'idée est que lorsque vous faites:

next = std::move(next->next);

L'ancien pointeur partagé nextest détruit (car il l' use_countest maintenant 0) et vous pointez sur ce qui suit. Cela fait exactement la même chose que le destructeur par défaut, sauf qu'il le fait de manière itérative plutôt que récursive et évite ainsi le débordement de pile.

Pour être honnête, je ne connais pas l'algorithme de désallocation de pointeur intelligent d'aucun compilateur C ++, mais je peux imaginer un algorithme simple et non récursif qui fait cela. Considère ceci:

• Vous disposez d'une file d'attente de pointeurs intelligents en attente de désallocation.
• Vous disposez d'une fonction qui prend le premier pointeur et le désalloue, et le répète jusqu'à ce que la file d'attente soit vide.
• Si un pointeur intelligent a besoin d'une désallocation, il est poussé dans la file d'attente et la fonction ci-dessus est appelée.

Par conséquent, il n'y aurait aucune chance pour que la pile déborde, et c'est beaucoup plus simple que d'optimiser un algorithme récursif.

Je ne sais pas si cela correspond à la philosophie des «pointeurs intelligents à coût presque nul».

Je suppose que ce que vous avez décrit ne causerait pas de débordement de pile, mais vous pourriez essayer de construire une expérience intelligente pour me prouver le contraire.

MISE À JOUR

Eh bien, cela prouve mal ce que j'ai écrit précédemment:

#include <iostream>
#include <memory>

using namespace std;

class Node;

Node *last;
long i;

class Node
{
public:
   unique_ptr<Node> next;
   ~Node()
   {
     last->next.reset(new Node);
     last = last->next.get();
     cout << i++ << endl;
   }
};

void ignite()
{
    Node n;
    n.next.reset(new Node);
    last = n.next.get();
}

int main()
{
    i = 0;
    ignite();
    return 0;
}

Ce programme construit éternellement et déconstruit une chaîne de nœuds. Cela provoque un débordement de pile.