Zwangsweise verwendung des Heaps

volkard

Ja, vielleicht den Thread http://www.c-plusplus.net/forum/297546

volkard

Ist die Liste der Besitzer der Objekte und für deren Zerstörung verantwortlich?
Löst eine intrusive Liste (wie so oft) alle Probleme?

Eigentlich hast Du zwei Listen: Die statischen Objekte und die Heap-Objekte.

Und die tust Du zu einer Liste zusammenkleben beim Start. Und beim Ende wieder auseinandernehmen. Das geht gut, wenn der statische Teil unberührt bleibt, zum Beispiel Systemfunktionen in der Bezeichnertabelle.
Anderenfalls müßtest Du wohl jedes Objekt fragen können, ob es auf dem Heap liegt und anhanddessen deleten oder nicht (langsam!, dann ist es schneller bei Programmstadt die paar Knoten auch noch auf dem Heap zu erzeugen.).

Oder Du läßt es eine Liste ohne Besitz sein und hast noch eine zweite, die sich nur um den Besitz und am Schluß das Aufräumen kümmert, in der nur die Heap-Objekte liegen.

hustbaer

"smart pointer" möchte ich nicht verwenden, da diese den Speicherverbrauch in der Liste erhöhen.

Also ein unique_ptr sollte genau gleich gross sein wie ein normaler Zeiger.

Es ist natürlich jetzt die Gefahr, dass der Benutzer dies Anforderung missachtet und trotzdem die Objekte auf dem Stapel erstellt. Dies will ich unterbinden.

Das grenzt schon an Quatsch.

knivil

Hier ist ganz klar nicht geklaert, wer den Zeiger "besitzt". Ist das eindeutig und halten sich alle daran, so gibt es keine Probleme. Stack- und Heapobjekte sind nicht unterscheidbar.

Es ist natürlich jetzt die Gefahr, dass der Benutzer dies Anforderung missachtet und trotzdem die Objekte auf dem Stapel erstellt. Dies will ich unterbinden.

Quasi dein Chef sagt, transportiere Objekt A nach Berlin. Er verraet dir aber nicht, wo Objekt A zu finden ist. Kannst du diese Aufgabe erfuellen?

Ich habe mich jetzt dafür entschieden, der Liste eine unique_ptr Referenz zu übergeben. Damit ist offensichtlich, dass der Speicher automatisch gemanaged wird. Und man hat immer noch die Option ein statisches Objekt einzugeben, wenn man den richtigen Destruktor mit gibt. Danke für den Hinweiß. Beste Lösung soweit. Offensichtlich lässt sich eine Zwangsweiße erstellung auf dem Heap in C++ nicht sauber implementieren. Zmindest ist mir keine ins Auge gesprungen.

Den Besitz kann ich der Liste nicht übergeben. Genau genommen dürfte sie die Objekte nicht löschen. Das müsste der Interpreter tun, der sie auch erstellt. Doch hierfür bräuchte ich eine zweite Liste. Das ist natürlich mit zusätzlichem Speicherverbrauch und Rechnerzyklen verbunden. Da zwei Listen parallel gemanaged werden müssten.

Jetzt stellt sich mir noch die Frage, wer denn den Besitz bei verwendung eines unique_ptrs hat?

Danke nochmal. Ihr habt mir sehr weitergeholfen.

SeppJ

Hast du dir eigentlich mal die anderen Stichworte angeguckt, die mehrmals gefallen sind? Ich hätte eigentlich erwartet, dass eine intrusive Liste die "beste" Lösung ist, der unique_ptr war eigentlich bloß so ein Vorschlag, wie man das was du dir selbst als Lösung ausgedacht hast umsetzen könnte.

Ich verwende eine Intrusive Liste, seit volkhard mich darauf gestoßen hat. Sie ist eindeutig effizienter. Aber ich sehe den Zusammenhang zum Problem nicht. Auch die Elemente der intrusiven liste müssen doch irgendwo im Speicher liegen?!

volkard

Martin Kalbfuß schrieb:

Ich verwende eine Intrusive Liste, seit volk**h**ard mich darauf gestoßen hat. Sie ist eindeutig effizienter. Aber ich sehe den Zusammenhang zum Problem nicht. Auch die Elemente der intrusiven liste müssen doch irgendwo im Speicher liegen?!

Mit der intrusiven Liste kannste alle Objekte halten zum Durchiterieren, suchen oder was Du so brauchst. Und eine andere Liste (z.B. std::list) kannste machen, um Freispeicherobjekte aufzubewahren oder so, also Besitz-Sachen machen. Die Stack-Objekte sind dann nur in der intrusiven Liste und die Freispeicher-Objekte sind in beiden Listen. An sowas hatte ich gedacht.

Ah,
Doppeltes Dankeschön an volkard. Jetzt habe ich deinen Hinweiß vollständig verstanden. Die Intrusive liste reserviert ja dür die Elemente selbst keinen Speicher. Somit ist der zusätzliche Speicherverbrauch duch zwei Listen sehr gering gehalten. Der Besitz ist somit eideutig geklärt und die Lösung trotzdem speichereffizient.

Martin Kalbfuß schrieb:

Ich verwende eine Intrusive Liste, seit volkhard mich darauf gestoßen hat. Sie ist eindeutig effizienter. Aber ich sehe den Zusammenhang zum Problem nicht. Auch die Elemente der intrusiven liste müssen doch irgendwo im Speicher liegen?!

Du redest die ganze Zeit von Effizenz und Speicherverbrauch. Hast Du mal daran gedacht, dass Listen dafür eigentlich gar nicht die beste Wahl sind? Weil:

a) Sie Pointer auf die anderen Listenelemente speichern müssen. Bei üblichen doppelt verketteten Listenobjekten, die laut deinen Infos sowieso nur Pointer auf Objekte speichern, ist der Speicherverbrauch für die Verwaltungsinfos schon mindestens doppelt so groß, wie der der eigentlichen Nutzdaten.

b) Listen, die nicht kontinuierlich gefüllt worden sind, führen zu vielen Page Faults im laufenden Programm.

So wie Du deine Anwendung beschrieben hast, wäre ein Vektor die bessere Wahl (Befüllung beim Start, irgendwann zur Laufzeit wird nur hinzugefügt, Löschen beim Ende), auch wenn er mal umkopiert werden muss, wenn er seine Kapazität vergrößert. Zugriff extrem schnell, Iterieren über den gesamten Vektor erfordert viel weniger Aufwand als über eine Liste.

Natürlich kann eine Liste für Dich trotzdem die beste Wahl sein, ich spreche das nur mal an, weil Du Effizienz und Speicherverbrauch in jedem 2ten Beitrag erwähnst und es mir scheint, dass Du Beides mit beiden Händen rauswirfst.

Es ist richtig, dass ich mir über den optimalen Container noch nicht im klaren bin. Es kann durch auß sein, dass dies sich später noch ändern wird. Die Wahl der Liste ist darauf zurück zu führen, dass diese die traditionell verwendete Datenstruktur ist. Mein Interpreter ist an FORTH angelehnt. Es gibt mit sicherheit bessere Lösungen. Z.b einen Binären Suchbaum. Oder gleich einen Parser.
Ich habe mich einfach dafür entschieden vorläufig die traditionelle Lösung beizubehalten. Das Wissen über Intrusive Container wird mir aber auch dann noch hilfreich sein.

Die Liste ist als Container zumindest brauchbar, da das Löschen der Elementente überall und jederzeit geschehen kann. Wann lässt sich auch nicht vorhersehen. Auch kann die Liste sehr lang werden. Hier wäre dann ein Vektor vielleicht ein wenig problematisch.

Ich hab mir das Problem mit den großen Konstanten der Liste zu Herzen genommen. Ich werde das ganze bei gegebener Zeit nochmal überdenken.

Martin Kalbfuß schrieb:

Die Liste ist als Container zumindest brauchbar, da das Löschen der Elementente überall und jederzeit geschehen kann. Wann lässt sich auch nicht vorhersehen. Auch kann die Liste sehr lang werden. Hier wäre dann ein Vektor vielleicht ein wenig problematisch.

Die Frage wäre hier, ob die Reihenfolge der Elemente in der Liste von Bedeutung ist. Ist sie das nicht, kann aus einem Vektor einfach ein Element gelöscht werden, indem man das letzte Element des Vektors an die Stelle des zu löschenden Elements kopiert. In deinem Fall also nur ein Pointer.

Die Reihenfolge ist leider bedeutend.