Ich habe mehrere lange verkettete Listen (sie haben bis zu 20.000 Artikel). Sie haben unterschiedliche Anfänge, können aber von einem Knoten an auf den gleichen Knoten zeigen. Ich habe beschlossen, eine solche verknüpfte Liste zusammenwachsen zu lassen und den Speicher zwischen ihnen zu teilen.
Deshalb habe ich beschlossen, eine verkettete Liste mit geteilten Zeigern zu implementieren:
%Vor%So 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 ihr nicht freigegebener Teil gelöscht.
Das Problem tritt auf, wenn längere verkettete Listen ohne freigegebene Teile gelöscht werden sollen. Löschen beginnt mit dem ersten Element. Dies verringert die Anzahl der Verweise auf das nächste Element, die ebenfalls gelöscht werden können, und dies wiederholt sich rekursiv, bis der Stapel überläuft.
Hier ist das Beispiel von Code, der eine lange verkettete Liste erstellt und dann nicht löscht.
%Vor%Ich danke im voraus für eines der folgenden:
Beachten Sie, dass diese Frage nicht C ++ 11 spezifisch ist. Es ist mir egal, welche Implementierung von geteilten Pointes verwendet wird. Ich habe sogar meine eigenen geteilten Zeiger implementiert. Dies erlaubte mir ein wenig längere verkettete Listen, aber die Rekursion in Destruktoren und Stack-Überlauf erschien ebenfalls. Und ich sehe keine Möglichkeit, wie geteilte Zeiger ohne Rekursion in Destruktoren implementiert werden können.
BEARBEITEN:
Nur um Verwirrungen zu vermeiden: Ich möchte wiederholen, dass die ganzen Listen geteilt werden können. So könnte man sie 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 nicht verschwenderisch durch 1,2,3,4,5,6,7 speichern, aber sie zeigen auf den gleichen Ort. Aus diesem Grund ist eine Referenzzählung erforderlich.
delete list3; soll nur den Teil löschen, der nicht freigegeben ist, d. h. die Elemente 10,11,12.
Wenn Sie shared_ptr verwenden, wird das Eigentum für Sie verwaltet. Wenn der Referenzzähler auf 0 geht, ruft er den Destruktor des Pointees auf. Jetzt wird das auf das Objekt zeigende Objekt zerstört und als ein Element davon der nächste gemeinsame Zeiger, der das nächste ... zerstört. Dies führt zu einer rekursiven Art der Speicherfreigabe. Jetzt könnten Sie versuchen, den Speicher iterativ freizugeben. Sie müssen nur einen Verweis auf das nächste Element behalten, um dessen Zerstörung zu vermeiden, und es später manuell löschen:
Im Allgemeinen ist shared_ptr wahrscheinlich nicht eine gute Idee für
verknüpfte Listen, aus dem Grund, wieso Sie darauf hinweisen. In diesem Fall, du
wahrscheinlich müssen Sie es von Hand tun, halten Sie eine Elternzahl in
jeder Knoten. (Es ist wahrscheinlich möglich, eine Art von
Schleife, die den Stapelüberlauf mit shared_ptr vermeidet, aber die
Die Ergebnisse wären wahrscheinlich komplexer als die Verwaltung des Speichers
von Hand.)
Tags und Links c++ c++11 data-structures recursion shared-ptr