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

[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.

[Cherup]

Mechanics schrieb:

Gefällt mir trotzdem nicht.

Mir gefällts auch nicht wirklich, das ist irgendwie... unschön. Mir fällt aber auch keine elegantere Lösung ein um den start- bzw end-Punkt einer Reihe von Nodes festzulegen um ein stopkriterium für iterieren über Schleifen zu erhalten. Bzw. mir fällt gerade möglicherweise schon eine Lösung ein. Muss ich aber erstmal durchdenken. Könnte in etwas "komplexeren" begin und end-Funktionen enden.

Ja, die Sentinelnodes sind nur normale Nodes mit anderem Namen. Es gibt 2 oder 3 stellen im Code wo ich den Node-Typ abfrage um ein löschen der Sentinels oder ein durchlaufen durch einen Iterator zu verhindern.
Wie gesagt, ganz glücklich bin ich nicht damit.

Mechanics schrieb:

Der Link von Swordfish passt doch perfekt zu deinem Code und deinen Fragen.

Das stimmt, ich war nur unsicher worauf du dich beziehst ich kannte den Begriff der atomaren Funktionen noch nicht.

Mechanics schrieb:

Besser wärs evtl. wieder mit Type Erasure.

Werd sehen was sich tun lässt

[Cherup]

So, das meiste an Umbau ist erledig, im wesentlichen fehlt nur noch der Umbau auf eine öffentliche Iterator-Klasse. Intern dürfte sich dadurch nichts ändern, da eh immer mit der abstrakten Basisklasse tree_iterator gearbeitet wird. Nach außen sollte es aber aufgeräumter wirken.

Bevor ich zu meiner eigentlichen Frage komme noch zwei Anmerkungen

Mechanics schrieb:

Initialisierungen mit nullptr schauen komisch aus.

Muss ich bei den Pointern zu den umgebenen Nodes aber machen. An etlichen Stellen wird abgefragt, ob sie Null sind bevor sie initialisiert werden. Das führt immer zu einem segmentation fault.

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?

Das ist auch soweit richtig. Das Problem ist, das ich um den Wert abfragen zu können den Pointer zu holder<T> casten muss. (Anmerkung: template<typename T> class holder : public placeholder, um type erasure zu ermöglichen). Das geht aber nicht mit unique_ptr. Sicher, ich kann den Pointer mit release() freigeben, den Wert abfragen und wieder dem unique_ptr zuweisen. Aber ist das nicht ein deutliches Mehr an Arbeit als ein shared_ptr mit einem einzelnen cast?
Wenn jemand eine bessere Zugriffsmöglichkeit kennt bitte verraten

Zur eigentlichen Frage:
Mir fällt es schwer ein sinnvolles Design für die Iteratoren zu finden und bevor ich wild drauf los schreibe frage ich besser mal nach.
Ich möchte den tree_iterator zum einzigen öffentlichen Iterator machen. Daher ist meine Designe-Idee folgende: Alle Iteratoren erben wie bisher die meisten Funktionen des tree_iterator, nur die 4 increment/decrement-Operatoren sind ja bei jedem Iterator verschieden und werden deshalb virtuell.
Die bisher öffentlichen unterschiedlichen Iteratoren werden innerhalb des tree_iterators gekapselt.
Soweit so gut.
Wobei ich Probleme habe ist zum einen in welchem scope sich der tree_iterator befinden soll, im namespace oder in der treeContainer-Klasse, die z.B. auch Node enthält.
Zum anderen, von wem ich die Iteratoren per Funktion bekomme? Vom tree_iterator selbst oder vom treeContainer? type erasure wird nach meinem Verständnis dadurch erreicht, das ja jeder Iterator von tree_iterator erbt und tree_iterator die in/decrement-Operatoren an die entsprechende Iterator-Klasse weiterleitet. Wenn ich also immer nur tree_iterator zurückgebe ist es ja egal, welcher Iterator da jetzt wirklich hintersteckt.
Dem tree_iterator gebe ich zwei Konstruktoren: Einen tree_iterator(), um einfach einen "leeren" Iterator mit "tree_iterator it()" erstellen zu können und einen tree-iterator(const tree_iterator& it), der den tree_iterator eben mit einem entsprechenden iterator initialisert.

Ist das Design sinnvoll?
Irgendwie steh ich total auf dem Schlauch...

[Mechanics]

Du musst einen shared_ptr nicht initialisieren, das macht sein Konstruktor. Deswegen ist es sinnlos, einem shared_ptr als Initialisierung nullptr zuzuweisen.

Was du mit den Casts und unique_ptr meinst, versteh ich nicht. Den Zeiger kannst du dir mit get rausholen und casten.

Der Vorteil von Type Erasure ist, dass man Objektsemantik bekommt/behält. Dann kann man mit dem Iterator als Objekt arbeiten. Sonst bräuchte man ja irgendeine Art von Zeigern, um polymorphes Verhalten zu ermöglichen. Und das ist bei einem Iterator nicht schön.
Wenn du das so ähnlich wie in der STL machst, wäre der Iterator eine Unterklasse des TreeContainers.
Macht es Sinn, einen ungültigen Iterator zu erstellen? Ich denke, nicht. Und die Klassen müssen irgendwie unterschiedlich heißen, sonst baust du einen Copy Constructor

[Cherup]

Mechanics schrieb:

Du musst einen shared_ptr nicht initialisieren, das macht sein Konstruktor.

Hab ich auch rausgenommen, nur die raw-pointer werden noch initialisiert, dachte du beziehst dich auch auf die.

Mechanics schrieb:

Den Zeiger kannst du dir mit get rausholen und casten.

Ähmmm, ja... *hust* *hoch rot anlauf* Jemand möge mich schlagen, soviel dummheit gehört bestraft!!!

Irgendwie versteh ich das mit den Iteratoren immer noch nicht, bin aber auch recht müde und ziemlich verwirrt...
Gut, tree_iterator als public Klasse in den treeContainer packen. Und die restlichen? Als private Klassen in den treeContainer packen? Und wenn man einen Iterator anfordert, z.B. mit
"treeContainer::tree_iterator it(Container->begin());"
wird durch die begin()-Funktion ein node_iterator zurückgegeben, der durch die Vererbung bzw. durch den Rückgabetype von begin() nach außen als ein tree_iterator erscheint?

Ansonsten schonmal der Changelog bis jetzt:
treeContainer:
- Zusammenfassung der RemoveToStart/RemoveToEnd-Funktionen zu einer remove(begin,end)-Funktion
- Ersetzen von find(tree_iterator pos, T value) für die Suche innerhalb eines Nodes durch ranged find(tree_iterator first, tree_iterator last, T value)
- Verbesserung/Vereinfachung der find()-Funktionen
- Anpassung der begin/end-Funktionen wegen des Entfernens der SentinelNodes

Node:
- Entfernung der SentinelNodes
- Entfernung der get/set-Funktionen für die Nodes

Iteratoren:
- Verbesserung der increment/decrement-Funktion der Iteratoren

Ja, es hat geklappt die doofen Sentinels wegzubekommen

[Mechanics]

Cherup schrieb:

Als private Klassen in den treeContainer packen? Und wenn man einen Iterator anfordert, z.B. mit
"treeContainer::tree_iterator it(Container->begin());"
wird durch die begin()-Funktion ein node_iterator zurückgegeben, der durch die Vererbung bzw. durch den Rückgabetype von begin() nach außen als ein tree_iterator erscheint?

Ich sehe den iterator im Moment am ehesten als einen Wrapper um sowas wie eine iterator_impl Klasse, die wiederum virtuelle Funktionen hat. Der Benutzer bekommt immer einen Iterator, die interne Implementierung unterscheidet sich aber.

[Cherup]

Jetzt bin ich endgültig verwirrt, ich raffs einfach nicht
Wie stehen denn dann die Klassen tree_iterator, Iterator_impl und die restlichen zueinander? wer erbt von wem? Wieso hat nicht der tree_iterator die Implementierung der meisten Befehle und leitet nur die increment/decrement-Operatoren über virtuelle Funktionen an die eigentlichen Iterator-implementierungen weiter? Außer den genannten Operatoren unterscheiden die sich doch nicht?
Ein Wrapper ist doch in dem Fall nichts anderes als eine Basisklasse, von der alle erben und die die virtuellen Funktionen weiterleitet, warum also durch eine weitere Klasse weiterleiten? Und wenn nur die Iterator_impl alle Funktionen hat, wie kann ich dann von außen auf die Funktionen zugreifen?

Kannst du mir einmal kurz die Abhängigkeiten schreiben? Ich glaube, dann würde ich es verstehen...