"Container" für beliebig viele Variablen eines beliebigen Types implementieren

[Cherup]

Morgen,

ich stehe immernoch vor dem selben Problem und verstehe das Verhalten einfach nicht.

Um das aktuelle Problem nochmal klar zu formulieren:
Ich entferne einen shared_ptr mit use_count = 3 und weak_count = 1 aus einem vector.
Dadurch wird der Destruktor des Objekts aufgerufen.
Das Objekt bleibt an der Speicheradresse erhalten, aber ein shared_ptr des Objekts wird durch den Destruktor gelöscht.

Das Problem ist, dass der Destruktor überhaupt aufgerufen wird. Es zeigen doch noch andere Pointer auf das Objekt?

Für mich sieht das Verhalten irgendwie so aus, als ob mit 2 verschiedenen Objekten gearbeitet wird, ich kann mir aber nicht erklären, woher das 2. Objekt kommen sollte...

Ich hoffe ihr könnt mir da weiterhelfen...
Aus irgendeinem Grund habe ich ziemliche Probleme mit shared_pointern

einen schönen Tag noch
Cherup

[Mechanics]

node* temp = myNodes[0]->getNode(4).get();
myNodes[2]->appendNode(shared_ptr<node>(temp));

Die Zeilen werden sich wahrscheinlich beißen.

[Cherup]

Morgen,

danke für den Hinweis, damit hattest du Recht.
Kannst du mir erklären, warum die sich beißen?

Ich hatte dass so geschrieben, damit es recht ähnlich zum Container ist. Dort bekomme ich auch einen Pointer vom Iterator und versuche ihn als shared_ptr an die appendNode()-Funktion zu übergeben.

Die einzige Lösung die mir spontan einfällt ist eine weitere Funktion vor der appendNode()-Funktion, die einen raw-Pointer bekommt, damit den passenden shared-ptr aus dem vector sucht und diesen dann zurückgibt.

Gibt es eine bessere/schnellere/elegantere Lösung?

[Mechanics]

Der shared_ptr übernimmt die Verwaltung des ref counters. Die Objekte sind nicht zwischen shared_ptr´n übertragbar.
Deswegen bin ich hier eigentlich für eine rein Iterator-basierte Lösung. Der Benutzer soll keine nodes oder shared_ptr sehen, nur Iteratoren und Daten. Sowas:

appendNode(const iterator& pos, const T& value);

Alles was mit nodes und Speicherverwaltung zu tun hat, würde ich vor dem Benutzer komplett verstecken.

[Cherup]

Danke für die Erklärung

Ich hatte mir deinen Hinweis zum Zugriff über Iteratoren auch zu Herzen genommen.
Die Problem-Funktionen sind im Wesentlichen intern in den Nodes, die können von den Benutzern nicht benutzt werden. Deshalb übergebe ich ja einen Iterator an die (öffentliche) move-Funktion, die dann die Operationen an den Nodes durchführt.
Allerdings ist halt der aktuelle Node als Pointer (genauer als raw-Pointer) im Iterator hinterlegt, sonst macht der ja wenig Sinn... Der Zugriff auf die Nodes funktioniert nur noch über die Container-Klasse und den Iterator und es kann nicht direkt auf die Nodes zugegriffen werden

Mir ist noch aufgefallen, dass ich noch sentinel-Nodes brauche, um das Ende der angehängten Node-Listen zu markieren und noch ein, zwei kleinigkeiten, dann sollte das soweit fertig sein...

[Mechanics]

Der Iterator kann ja dann auch einen shared_ptr oder weak_ptr statt einem raw pointer speichern, wenn du das so brauchst.

[Cherup]

Schönen guten Tag in die Runde,

nach langer Pause habe ich endlich die Zeit gefunden am Container weiter zu arbeiten.

Er sollte jetzt grundsätzlich fertig sein, sprich alle Funktionen laufen in meinem Test so wie sie sollen, die Funktionalität sollte komplett sein, Sentinel-Nodes sind vorhanden und es kann ausschließlich über die Containerklasse an sich und die Iteratoren gearbeitet werden.

Ich denke, dass noch Potential für Verbesserungen vorhanden ist, insbesondere was meine "heißgeliebten" (Vorsicht, freilaufene Ironie!) Pointer angeht.

Wer sich den 1100 Zeilen umfassenden Spaß ansehen möchte, der Code ist unter

http://pastebin.com/UbYBMr6A (TreeContainer.h)
http://pastebin.com/DH1UXxWF (TreeContainer.cpp)

zu finden.

Über Verbesserungen, Anmerkungen, konstruktive(!!!) Kritik usw. freue ich mich natürlich wie immer

Viele Grüße
Cherup

[hustbaer]

Was macht tree_iterator::Next() ? Wird die Funktion irgendwo aufgerufen?

Und ich würde sagen du solltest erstmal alle Member und Funktionen deiner Implementierung dokumentieren. Sieht für mich so aus als ob da einiges total umständlich und/oder redundant implementiert wäre. Und ich persönlich hab' zumindest keine Lust mir sowas genauer anzusehen. Also mir Code anzusehen der stark den Eindruck macht übermässig kompliziert und vielleicht sogar fehlerhaft zu sein, und gleichzeitig nicht ausreichend kommentiert ist.

[Cherup]

Ups, mit der Doku hast du recht, das werde ich noch nachbessern.

Übermäßig kompliziert sollte es eigentlich nicht sein. Teilweise recht komplex, das ja, aber ich habe versucht den Code so einfach wie möglich zu halten. Mag gut sein, dass es an einigen Stellen noch Vereinfachungen gibt, da sind mir keine besseren Lösungen eingefallen. Wenn sowas auffällt und eine bessere Lösung bekannt ist bitte melden

Fehlerhaft sollte das Ganze nicht mehr sein, zumindest treten in meinem Test keine mehr auf. Auch da bitte melden Ich kenne ein oder zwei Schwächen, die sich aber nicht als Fehler bemerkbar machen sollten (z.B. benutzung der begin()-Funktion als Abbruchstatement bei einem Reverse-Iterator. Dafür gibts schließlich rend()),

Nur so nebenbei, Next() setzt den Iterator einfach auf den nächsten Node in der Reihe, bzw. auf den Parent, sofern das Ende erreicht ist. Dient dem manuellen Navigieren durch den Tree, da der ++-operator auch die Kinder durchläuft und das nicht unbedingt immer gewünscht ist.

Wie sieht denn deiner Meinung nach eine vernünftige Doku aus? Eine kurze Funktionsbeschreibung mit den angenommenen Parametern und der Rückgabe der Funktion als Kommentar über der Funktion?

Schönen Abend
Cherup

[Mechanics]

Mir fehlt auf den ersten Blick so ein bisschen const... Ich hätte mehr const erwartet Und mehr &.
Ich hatte mir das am Anfang wenn ich mich recht erinnere etwas genauer angeschaut, aber mittlerweile kann ich mich an kaum was erinnern und es zu viel Code, um sich reinzudenken.

p.s. Vielleicht wären paar Beispiele gut. Wenn man sich die API anschaut, hat man schon mal einen Eindruck, obs einem gefällt oder nicht, und dann kann man sich mal die Implementierung genauer anschauen. Sonst hängt die Implementierung so ein bisschen in der Luft und man weiß nicht so recht, wofür das alles genau gut ist.

[hustbaer]

Cherup schrieb:

Wie sieht denn deiner Meinung nach eine vernünftige Doku aus?

z.B. genau das was du gerade zur "Next" Funktion geschrieben hast.

Was mir davon abgesehen noch fehlt:
* Ne Beschreibung um welche Art Baum es sich überhaupt handelt (mag sein dass diese Info hier im Thread zu finden ist, aber die sollte mMn. auch in den Code)
* Ne beschreibung was die ganzen Member alle machen. Deine Nodes haben ja nicht gerade wenig Member, da frag' ich ich wozu die alle gut sind. Mag sein die haben alle nen Sinn, mag sein nicht. Ich bin mittlerweile (leider) so sehr an schlimmen bis furchtbaren Code gewöhnt dass ich im Zweifelsfall erstmal von "macht keinen Sinn" ausgehen.

[Cherup]

Danke für die Hinweise,

an der Uni lernt man zwar grundlegend programmieren aber weder einen guten Stil noch wie eine anständige Doku auszusehen hat bzw. dass sie überhaupt vorhanden sein sollte.

Das ist ein Grund warum ich den Spaß hier überhaupt mache und warum ich viel Wert auf Antworten von erfahrenen Leuten lege (auch wenn es manchmal etwas ärgerlich ist wenn die Arbeit zerissen wird ). Ist bei dem Umfang des Codes aber auch verständlich, dass man sich da bzw. in der Form nicht einarbeiten möchte.

Ich bin dabei eine (hoffentlich) anständige Doku zu erstellen und const einzubauen. Dabei muss ich den Code an wenigen Stellen nochmal überarbeiten. Zum Glück, denn dadurch ist mir ein tatsächliches Problem aufgefallen.
Es geht dabei um die remove()-Funktionen, die einen jetzt const Iterator& bekommen und den Knoten, auf den der Iterator zeigt, löscht.
Dadurch hängt der Pointer des Iterators natürlich sozusagen in der Luft.

Mein Lösungsansatz dazu ist, einen temporären Pointer auf den zu löschenden Node zu erstellen, den Iterator auf einen anderen Node zu setzen (previous, next oder parent) und dann den Node zu löschen.
So weit so gut, ABER...
Der Iterator ist ja const, daher kann ich ihn nicht so ohne weiteres verändern, also nicht auf einen anderen Node setzen.

Jetzt ist die Frage, wie man das am besten löst. Mein naiver Lösungsansatz wäre 2 weitere private (tree darf darauf zugreifen, der User nicht) const Funktionen im Iterator zu erstellen, die die entsprechenden Iterator Funktionen aufrufen.

Vereinfacht dargestellt so:

class tree_iterator{
    friend class tree;
public:
    void Next() {...} //setzt den Iterator auf den nächsten Node
    void Prev() {...} //setzt den Iterator auf den vorherigen Node

private:
    void setNext() const { Next(); } //Next() für const Aufrufe
    void setPrev() const { Prev(); } //Prev() für const Aufrufe

private:
    Node* myNode;
};

Ist das so überhaupt möglich? Gibt es einen sinnvolleren Weg?

Viele Grüße
Cherup

[Mechanics]

Cherup schrieb:

an der Uni lernt man zwar grundlegend programmieren aber weder einen guten Stil noch wie eine anständige Doku auszusehen hat bzw. dass sie überhaupt vorhanden sein sollte.

Das ist ein Grund warum ich den Spaß hier überhaupt mache und warum ich viel Wert auf Antworten von erfahrenen Leuten lege

Das Studium ist auch nicht dazu da, programmieren zu lernen. Doku aber schon eher, kommt drauf an, was für Kurse man belegt. Grad bei der Softwarearchitektur ist Doku für verschiedene Stakeholder wichtig, und das ist schon eher was fürs Studium.

Cherup schrieb:

Es geht dabei um die remove()-Funktionen, die einen jetzt const Iterator& bekommen und den Knoten, auf den der Iterator zeigt, löscht.

Das ist ja soweit ok. Bei den std Klassen wird der Iterator auch ungültig, wenn man ein Element löscht. Deswegen gibt z.B. std::vector::erase einen neuen Iterator zurück und der alte wird ungültig.

[Cherup]

Mechanics schrieb:

Das Studium ist auch nicht dazu da, programmieren zu lernen.

Das ist wahr. Ist auch ein Grundlagenkurs gewesen.

Mechanics schrieb:

Das ist ja soweit ok. Bei den std Klassen wird der Iterator auch ungültig, wenn man ein Element löscht.

Danke für die Info, das wußte ich bisher noch nicht (oder habs ignoriert oder vergessen )

[Cherup]

Sooo,

jetzt ist jede menge const und & drin
Und eine hoffentlich ausreichende Doku

Ihr findet den dokumentierten Code unter

http://pastebin.com/v2SMS23E (treeContainer.h)
http://pastebin.com/TMvCTrZ1 (treeContainer.cpp)

Hinweise auf Verbesserungen (am Code oder der Doku) werden wie immer gerne angenommen

Viele Grüße
Cherup

[Mechanics]

remove, removeToEnd und removeToStart schauend redundant aus, ein remove(from, to) sollte reichen.

Aber Classes wird die Doku etwas komisch, finde ich. Node, SentinelNode. Warum braucht man eine SentinelNode Klasse und warum steht die in der Doku???
Member: std::shared_ptr myRoot. Kann an der Stelle noch nichts damit anfangen, finde ich nur den Namen komisch. Zur Info: das My in MySql ist der Name der Tochter des Entwicklers. Ich gehe davon aus, dass du keine Tochter mit diesem Namen hast, also ist die Bezeichnung myRoot nicht so cool.

Iteratoren: It iterates through all node until - böser Rechtschreibfehler!
Ich weiß nicht, obs mir gefällt, dass es verschiedene Klassen für Iteratoren gibt. Vielleicht ist es besser so, ich bin nicht tief genug drin in der Thematik. Spontan hätte ich aber eher erwartet, dass es nur eine öffentliche Iterator Klasse gibt und dafür verschiedene Funktonen, um einen zu bekommen:
iterator childIterator();
iterator nodeIterator();
Intern können die dann unterschiedliche Implementierungen haben. Es wäre einfacher, solche Iteratoren als Parameter zu übergeben und man müsste sich nicht um so viele Details kümmern. Aber wie gesagt, kann ich spontan nicht wirklich beurteilen.

std::shared_ptr<placeholder> myValue = nullptr;
Initialisierungen mit nullptr schauen komisch aus. Das ist eine RAII Klasse, die hat einen vernünftigen Default Constructor. Und wegen my hab ich schon was geschrieben.
Viele Getter Funktionen sind noch nicht const. Und shared_ptr am besten auch als const& übergeben. Atomare Operationen sind nicht soo billig, wenn man die sich sparen kann, gibt es keinen Grund, das nicht zu tun.

std::vector<std::shared_ptr<Node>> myChildren;
Da muss ich mich erst recht fragen, warum du irgendwelche Sentinel brauchst.

remove sollten normalerweise einen Iterator auf das nächste Element zurückgeben und nicht auf das vorherige.

std::shared_ptr<placeholder> myValue = nullptr;
Auf den ersten Blick... Warum hält der Node den Wert als shared_ptr? Er müsste doch eigentlich die Ownership haben?

Bei internen Klassen würde ich nicht so viele Getter und Setter machen, das ist eher Boilerplate.

Naja, über den eigentlichen Code hab ich kaum drübergeschaut, das ist viel schwieriger zu lesen, als eine Doku.

[Cherup]

Danke für die vielen Hinweise und mit vielem hast du Recht.
Das my ist eine alte Angewohnheit aus der Zeit als ich programmieren gelernt habe. Habs mir noch nicht abgewöhnt.

Mechanics schrieb:

Node, SentinelNode. Warum braucht man eine SentinelNode Klasse und warum steht die in der Doku???

Warum die SentinelNodes? Um eindeutige Start- und Endpunkte für die Iteratoren, insbesondere die child_iteratoren zu schaffen. Wenn man mit einer Schleife durchiteriert braucht man ein Abbruchstatement. Das wird durch die end() funktion gegeben. Dazu muss die end()-Funktion aber auf einen Node hinter dem letzten bzw. vor dem ersten Node zeigen, sonst wird eben nur bis zum vorletzten node iteriert.
Warum in der Doku? Einfach der Vollständigkeit halber, ist vielleicht eine ungünstige Stelle dafür.

Mechanics schrieb:

iterates through all node until - böser Rechtschreibfehler!

*hust* dazu sage ich mal besser nichts...*schäm*

Mechanics schrieb:

eine öffentliche Iterator Klasse gibt und dafür verschiedene Funktonen, um einen zu bekommen:

Der Punkt geht an dich, hab ich nicht dran gedacht. Zumal es ja eine (wenn auch abstrakte) Basisklasse für die Iteratoren gibt.

Mechanics schrieb:

Atomare Operationen sind nicht soo billig

Was meinst du damit? Direkt auf die Node-Member zugreifen? Ist problemlos möglich, aber ist das nicht etwas unschön/unsauber?

Mechanics schrieb:

std::vector<std::shared_ptr<Node>> myChildren;
Da muss ich mich erst recht fragen, warum du irgendwelche Sentinel brauchst.

Die nodes in dem vector sind nicht zwangsläufig in der Reihenfolge, in der sie am Node hängen. Wegen den sentinels siehe oben

Mechanics schrieb:

remove sollten normalerweise einen Iterator auf das nächste Element zurückgeben und nicht auf das vorherige.

Danke für den Hinweis, werds anpassen.

Mechanics schrieb:

std::shared_ptr<placeholder> myValue = nullptr;
Auf den ersten Blick... Warum hält der Node den Wert als shared_ptr? Er müsste doch eigentlich die Ownership haben?

Öhhh das stammt noch aus dem Code von vor 4 Monaten. Hatte glaube ich bei irgendwas Probleme mit dem unique-ptr und habs jetzt schlicht übersehen.

Mechanics schrieb:

Bei internen Klassen würde ich nicht so viele Getter und Setter machen, das ist eher Boilerplate.

Also direkt auf die Member zugreifen?

Vielen Dank für die vielen Hinweise und die Mühe die du schon in mein kleines Projekt gesteckt hast
Jipie, ich lerne endlich mal, wie anständiger Code auszusehen hat

[Swordfish]

Cherup schrieb:

Mechanics schrieb:

Atomare Operationen sind nicht soo billig

Was meinst du damit? Direkt auf die Node-Member zugreifen? Ist problemlos möglich, aber ist das nicht etwas unschön/unsauber?

GotW #91 Solution: Smart Pointer Parameters

[Cherup]

Ok,

ich weiß jetzt, das atomare Funktionen Funktionen sind die bei der Ausführung nicht unterbrochen weren. Verstehe ich noch nicht zu 100% weil ich noch nicht direkt mit multithreading zu tun hatte aber Ok.

Ich verstehe allerdings den Zusammenhang mit meinem Code noch nicht bzw. bin mir unsicher. Beziehst du dich auf einzeiler Funktionen? Und/oder auf helper Funktionen wie LinkNodes() der Node Klasse?

Die sind nicht wirklich notwendig, das ist mir bewußt, ich hatte sie eher aufgrund von Code-Redundanz und einer besseren Verständlichkeit des Codes geschrieben.

Nochmals vielen Dank an alle, die mir hier helfen und sich damit beschäftigen wollen, ich freue mich da ungemein drüber

Noch ein PS:
Ich überlege mir grade, wie ich remove(first,last) am besten schreibe.
Dabei ist mir ein mehr oder weniger kleines Problem aufgefallen. Was passiert, wenn first und last vertauscht sind? Also wenn der last VOR dem first node ist. Sollte ich da eine Prüfung einbauen oder dem Benutzer die korrekte Benutzung überlassen und einen Fehler riskieren?
Ich neige dazu immer alles möglichst abzusichern und von einem DAU ("Dümmster anzunehmender User") auszugehen

Und noch eine andere Frage stellt sich mir:
Wenn ich den shared_ptr eines Nodes lösche wird er ja zerstört. Was aber passiert, wenn dieser Node auch shared_ptr besitzt? Wird der Node dann trotzdem zerstört und die nodes der shared_ptr ebenfalls? Aus dem Bauchgefühl würde ich sagen ja bin aber nicht sicher.

[Mechanics]

Cherup schrieb:

Warum die SentinelNodes? ...

Gefällt mir trotzdem nicht. Bzw., mir ist auch nicht ganz klar, wie das implementiert ist... Ich hab im Source gesucht, und es gibt nicht viele Stellen, wo "Sentinel" vorkommt. Sind es einfach ganz normale Knoten? Warum ist es dann eine eigene Klasse, die von Node abgeleitet ist? Die scheint nichts zu machen.

Cherup schrieb:

Zumal es ja eine (wenn auch abstrakte) Basisklasse für die Iteratoren gibt.

Besser wärs evtl. wieder mit Type Erasure.

Cherup schrieb:

Also direkt auf die Member zugreifen?

Ja. Da das interne Objekte sind, bringt Kapselung nicht wirklich was. Außerdem ist es eh nicht wirklich gekapselt, wenn du für sowieso für alles getter und setter hast.

Der Link von Swordfish passt doch perfekt zu deinem Code und deinen Fragen. Ich wollte darauf hinaus, dass shared_ptr als const& und nicht als Kopie übergeben werden sollte, und in dem GotW wird auch genau erklärt, warum. Das Inkrementieren und Dekrementieren des shared_ptr Counters ist atomar und damit mit bestimmten Kosten verbunden. Außerdem wird da auch erklärt, warum man Objekte besser als Referenzen oder Zeiger und nicht als shared_ptr übergibt. Weil es die Funktion idealerweise eben nichts angeht, wie die Argumente die als Parameter übergeben werden verwaltet werden.

Ich weiß jetzt gar nicht, wie sich std::vector verhält, wenn die Iteratoren vertauscht sind. Hab ich noch nie ausprobiert und seh in der Doku auf den ersten Blick nichts dazu. Könnte mir vorstellen, dass es durch ein debug assert abgefangen wird und das wars dann.