Wird das Zerstören einer großen Liste meinen Stapel überlaufen?

Betrachten Sie die folgende Implementierung einer einzeln verknüpften Liste:

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

Angenommen, ich verwende std::unique_ptr<node> headkeine Instanz mehr, die dann außerhalb des Gültigkeitsbereichs liegt und deren Destruktor aufgerufen wird.

Wird dies meinen Stapel für ausreichend große Listen sprengen? Ist es fair anzunehmen, dass der Compiler eine ziemlich komplizierte Optimierung durchführt (Inline unique_ptr-Destruktor in node's, dann Schwanzrekursion verwenden), die viel schwieriger wird, wenn ich Folgendes tue (da der dataDestruktor die verschleiern würde next, was es schwierig macht damit der Compiler die potenzielle Neuordnungs- und Tail-Call-Möglichkeit bemerkt):

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

Wenn es datairgendwie einen Zeiger nodedarauf gibt, kann es sogar unmöglich sein, den Schwanz zu rekursieren (obwohl wir uns natürlich bemühen sollten, solche Verstöße gegen die Kapselung zu vermeiden).

Wie soll man diese Liste dann im Allgemeinen sonst zerstören? Wir können die Liste nicht durchlaufen und den "aktuellen" Knoten löschen, da der gemeinsam genutzte Zeiger kein release! Der einzige Weg ist mit einem benutzerdefinierten Deleter, der für mich wirklich stinkt.

Ja, dies wird irgendwann Ihren Stack sprengen, es sei denn, der Compiler wendet zufällig eine Tail-Call-Optimierung auf nodeden Destruktor und shared_ptr den Destruktor an. Letzteres hängt stark von der Standardbibliotheksimplementierung ab. Die STL von Microsoft wird dies beispielsweise niemals tun, da shared_ptrzuerst der Referenzzähler des Pointees (möglicherweise das Objekt zerstört) und dann der Referenzzähler des Steuerblocks (der schwache Referenzzähler) dekrementiert wird. Der innere Destruktor ist also kein Tail Call. Es ist auch ein virtueller Anruf , der es noch weniger wahrscheinlich macht, dass er optimiert wird.

Typische Listen umgehen dieses Problem, indem nicht ein Knoten den nächsten besitzt, sondern ein Container, der alle Knoten besitzt, und eine Schleife verwendet, um alles im Destruktor zu löschen.

Späte Antwort, aber da niemand sie zur Verfügung gestellt hat ... Ich bin auf dasselbe Problem gestoßen und habe es mithilfe eines benutzerdefinierten Destruktors gelöst:

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

Wenn Sie wirklich eine Liste haben , dh jedem Knoten ein Knoten vorausgeht und höchstens einen Follower hat und Sie listein Zeiger auf den ersten sind node, sollte das oben Genannte funktionieren.

Wenn Sie eine unscharfe Struktur haben (z. B. ein azyklisches Diagramm), können Sie Folgendes verwenden:

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

Die Idee ist, dass wenn Sie:

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

Der alte gemeinsame Zeiger nextwird zerstört (weil er use_countjetzt ist 0), und Sie zeigen auf Folgendes. Dies entspricht genau dem Standard-Destruktor, außer dass dies iterativ statt rekursiv erfolgt und somit ein Stapelüberlauf vermieden wird.

Um ehrlich zu sein, bin ich mit dem Algorithmus zur Freigabe intelligenter Zeiger eines C ++ - Compilers nicht vertraut, aber ich kann mir einen einfachen, nicht rekursiven Algorithmus vorstellen, der dies tut. Bedenken Sie:

• Sie haben eine Warteschlange mit intelligenten Zeigern, die auf die Freigabe warten.
• Sie haben eine Funktion, die den ersten Zeiger nimmt und die Zuordnung aufhebt und dies wiederholt, bis die Warteschlange leer ist.
• Wenn ein intelligenter Zeiger eine Freigabe benötigt, wird er in die Warteschlange gestellt und die obige Funktion wird aufgerufen.

Daher besteht keine Chance, dass der Stapel überläuft, und es ist viel einfacher, einen rekursiven Algorithmus zu optimieren.

Ich bin mir nicht sicher, ob dies in die Philosophie der "fast Null-Kosten-Smart-Pointer" passt.

Ich würde vermuten, dass das, was Sie beschrieben haben, keinen Stapelüberlauf verursachen würde, aber Sie könnten versuchen, ein cleveres Experiment zu erstellen, um mir das Gegenteil zu beweisen.

AKTUALISIEREN

Nun, das erweist sich als falsch, was ich zuvor geschrieben habe:

#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;
}

Dieses Programm baut ewig eine Kette von Knoten auf und dekonstruiert sie. Dies führt zu einem Stapelüberlauf.