Ich habe eine Reihe von langen verknüpften Listen (sie haben bis zu 20.000 Elemente). Sie haben unterschiedliche Anfänge, können aber irgendwann von einem Knoten auf denselben Knoten verweisen. Ich habe beschlossen, eine solche verknüpfte Liste zusammenwachsen zu lassen und die Erinnerung zwischen ihnen zu teilen.

Aus diesem Grund habe ich beschlossen, verknüpfte Listen mit gemeinsamen Zeigern zu implementieren:

#include <memory>
struct SharedLinkedList {
    int someData;
    std::shared_ptr<SharedLinkedList> next;
};

Auf diese Weise funktioniert alles gut. Die nicht mehr benötigten verknüpften Listen werden gelöscht. Wenn sie einen Teil mit einer anderen verknüpften Liste teilen, wird nur der nicht gemeinsam genutzte Teil gelöscht.

Das Problem tritt auf, wenn längere verknüpfte Listen ohne gemeinsam genutzte Teile gelöscht werden sollen. Das Löschen beginnt mit dem ersten Element. Dies verringert die Anzahl der Verweise auf das nächste Element, das ebenfalls gelöscht werden kann, und dies wiederholt sich rekursiv, bis der Stapel überläuft.

Hier ist das Beispiel für Code, der eine lange verknüpfte Liste erstellt und diese dann nicht löscht.

SharedLinkedList* beginningOfList;
SharedLinkedList* actualElement = new SharedLinkedList();
SharedLinkedList* nextElement;

beginningOfList = actualElement;
for (int i = 0; i < 1000; i++) { // 100 is OK, 1000 is KO
    nextElement = new SharedLinkedList();
    actualElement->next = std::shared_ptr<SharedLinkedList>(nextElement);
    actualElement = nextElement;
}
delete beginningOfList;

Ich bedanke mich im Voraus für eines der folgenden Dinge:

Erklärung der shared_pointers und was ich vermisse. Wie kann ich sie benutzen? Und kann das überhaupt mit ihnen gemacht werden? Ist eine solche gemeinsame Nutzung von Erinnerungen nicht das, wofür die Zeiger erfunden wurden?Ratschläge zum erneuten Implementieren meines CodesDieser Code wird für wissenschaftliche Berechnungen verwendet, die auf meinem Computer ausgeführt werden. Kann ich irgendwie etwas optimieren, um einen größeren Stapel zu haben?

Beachten Sie, dass diese Frage nicht C ++ 11-spezifisch ist. Es ist mir egal, welche Implementierung von Shared Pointes verwendet wird. Ich habe sogar meine eigenen geteilten Zeiger implementiert. Dies ermöglichte es mir, ein wenig länger verknüpfte Listen zu haben, aber die Rekursion in Destruktoren und das Überlaufen von Stapeln erschienen ebenfalls. Und ich sehe keine Möglichkeit, wie gemeinsame Zeiger ohne Rekursion in Destruktoren implementiert werden könnten.

BEARBEITEN:

Nur um Verwirrungen zu vermeiden: Ich möchte wiederholen, dass die ganzen Listen geteilt werden können. Man könnte sie also Bäume nennen.

Hier ist das Beispiel:

list1 enthält: 1,2,3,4,5,6,7.

list2 enthält: 6,6,6,1,2,3,4,5,6,7

list3 enthält: 10,11,12,1,2,3,4,5,6,7

Ich möchte dies in 3 SharedLinkedList darstellen, die keine Zeit verschwenden, indem sie 1,2,3,4,5,6,7 mehrmals speichern, aber auf denselben Ort verweisen. Aus diesem Grund ist eine Referenzzählung erforderlich.

delete list3; soll nur den Teil löschen, der nicht gemeinsam genutzt wird, d. h. die Elemente 10, 11, 12.