Zwangsweise verwendung des Heaps
-
Vorgestern, vom gleichen Autor:
http://http://www.c-plusplus.net/forum/297557Unterschiedliche Behandlung von Stack und Heap ist eine ganz ganz ganz schlechte Idee aus vielen Gründen, die hier schon in vielen Threads diskutiert wurden. Außerdem leuchtet mir nicht ein, wieso es einem Container etwas ausmachen sollte, worauf seine Elemente zeigen. Wenn der Container die Elemente nachträglich freigibt, dann übergib ihm den Besitz der Objekte, dann brauchst du keine Smartpointer (zumindest keine mit Overhead gegenüber normalen Pointern, ein einfacher unique_pointer sollte dir das Leben trotzdem einfacher machen). Und wenn der Container die Elemente nicht besitzt, dann hat er verdammt noch mal die Finger davon zu lassen!
Guckst du z.B. hier:
http://www.c-plusplus.net/forum/206880
oder hier:
http://http://www.c-plusplus.net/forum/280048
-
Martin Kalbfuß schrieb:
Es ist natürlich jetzt die Gefahr, dass der Benutzer dies Anforderung missachtet und trotzdem die Objekte auf dem Stapel erstellt.
Da Stackobjekte automatisch bei Verlassen des Scopes zerstört werden, wird kein vernünftiger Mensch auf die Idee kommen, Zeiger darauf in einem Container mit größerem Geltungsbereich zu verwalten.
-
Nein, http://www.c-plusplus.net/forum/297546 war's.
-
Es gibt eine Funktion namens remove. Diese Funktion löscht ein Element der Liste.
Die Funktion weiß nicht woher das Element stammt und wo es sich im Speicher befindet. Trotzdem muss sie einwandfrei funktionieren, unabhängig vom Typ. Statische Objekte sind nicht zwangsweise Kurzlebiger als der Container. Sie könnten in einer übergeorneten Funktion oder Global erstellt worden sein. In diesem Fall wird die funktion remove versagen, solange sie nichts genaueres über den Ursprung des Objektes weiß. Ich kann natürlich sagen, sch*** drauf. Wer statische Variablen benutzt ist eh doof. Scheint mir aber nicht der richtige Weg zu sein um eine Bibliothek zu entwerfen. Dem Container sollen sowohl beim Start des Programs Objekte hinzugefügt werden(Der Grundwortschatz), als auch später zur Laufzeit, durch Kombination der Worte des Grundwortschatzes durch den Benutzer des Interpreters. Letzteres muss über den Heap geschehen. Der Grundwortschatz wird aber nicht selbstverständlicherweise auf dem Heap angelegt. Ganz im Gegenteil. Es gibt keinen Grund ihn erst zur Laufzeit zu erstellen. Er muss aber durch oben erwähnte Funktion genauso enfernbar sein wie die durch den Interpreter hinzugefügten Worte. Für dem Endbenutzer gibt es keinen Unterschied zwischen Grundwortschatz und erweitertem Wortschatz. So sollte es zumindest sein. Damit die Funktion remove also tadellos funktioniert müssen alle enthaltenen Objekte vom Heap stammen. Denke ich zumindest.
Und genau dies will ich erzwingen. Aber eben ohne die Vererbung zu behindern. Protected Construktor + static factory sind zwar funktionell, erschweren aber eben die Vererbung, da jedes mal ne neue Fabrik angelegt werden muss. Außerdem Existiert hier kein Zwang mehr. Protected ist nicht sicher.Ich hoffe ich konnte die Situation ein wenig besser darstellen.
Übersehe ich hier etwas?Vielen dank nochmal.
Martin
-
Ja, vielleicht den Thread http://www.c-plusplus.net/forum/297546
-
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.
-
"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.
-
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.
-
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?!
-
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.
