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

[Cherup]

So wenig Anmerkungen? Das freut mich
Ja an einigen Stellen gibt es sicherlich noch Optimierungsmöglichkeiten.

Mechanics schrieb:

bei den Iteratoren noch zu viele Heap Operationen im Spiel sind

Was meinst du mit Heap-Operationen?

Mechanics schrieb:

Was ist an dem Iterator eigentlich genau dynamisch?

Wie meinst du das?

Mechanics schrieb:

Vielleicht könnte man das Verhalten und die Daten so ein bisschen von einander trennen

Das Verhalten und die Daten sind doch getrennt? Abgesehen davon, das die Iteratoren einen Node-Zeiger haben (was sie ja auch brauchen) habe die Iteratoren doch nichts mit den eigentlichen Daten zu schaffen?

Ansonsten würde ich sagen, das der Container vorläufig fertig ist
Danke nochmal für die viele Mühe.

Viele Grüße
Cherup

[Mechanics]

Heap Operationen sind new und delete. Die sind relativ langsam und es wäre eigentlich nicht schlecht, wenn man die vermeiden könnte.

Ich meinte, dass bei den Iteratoren wahrscheinlich das Verhalten dynamisch ist, die Daten aber wahrscheinlich für alle Iteratoren gleich sind (ein Node Zeiger). Korrigiere mich, wenn ich falsch liege.
Und wenn die Daten eh statisch sind, könnte man doch eigentlich auf new/delete und Zeiger verzichten. Die einfachste Möglichkeit wäre ein enum IteratorStrategy und dann ein switch case. Oder ein Struct mit Funktionszeigern, die einen Zeiger auf die Daten bekommen.

Was mir nämlich konkret nicht so gefällt ist, dass Operatoren wie ++ Heap Operationen benötigen. Wenn man die API etwas ändern würde, könnte man darauf wohl verzichten, in dem der iterator_impl einfach geändert wird. Aber da die Operatoren noch einen anderen Iterator zurückgeben müssen, und das Verhalten der Iteratoren dynamisch ist, braucht man eben Heap Operationen. Deswegen der Vorschlag mit der Optimierung.

[Cherup]

Mechanics schrieb:

die Daten aber wahrscheinlich für alle Iteratoren gleich sind (ein Node Zeiger). Korrigiere mich, wenn ich falsch liege.

Damit liegst du richtig.

Allerdings sind die einzigen Operatoren, die Heap-Funktionen brauchen die Post_increment und Post-decrement Operatoren.
Ich habe bis jetzt keinen Implementierungsvorschlag gesehen, bei dem das anders wäre, daher wüßte ich nicht, wie man das durch eine Änderung an der API beseitigen könnte.

Soweit ich das beurteilen kann, kommen die heap_operationen sonst fast nur bei Funktionen zum Einsatz, bei denen auch ein neuer Iterator zurückgegeben werden soll.
Ok, es gibt die eine oder andere Funktion, die ich aus einer anderen Funktion aufrufe und deshalb neue Iteratoren erstellen muss, das betrifft z.B. die clear()-Funktionen. Da geschieht das aber nur einmal. So ganz glücklich bin ich damit noch nicht. Auf der anderen Seite müsste ich sonst entweder neue private Funktionen erstellen (was ich nicht möchte) oder Funktionen redundant implementieren, was eine Änderung/Optimierung erschweren kann und fehleranfälliger ist.

Mechanics schrieb:

Und wenn die Daten eh statisch sind, könnte man doch eigentlich auf new/delete und Zeiger verzichten.

Geb ich dir Recht mit. Das würde bedeuten, das man nur einen einzigen iterator (den tree_iterator) hat, der aber verschiedene Iteratortypen simuliert, korrekt?

[Mechanics]

Cherup schrieb:

Geb ich dir Recht mit. Das würde bedeuten, das man nur einen einzigen iterator (den tree_iterator) hat, der aber verschiedene Iteratortypen simuliert, korrekt?

Ja, das wäre die etwas plumpere Lösung als die jetzige, die sich aus Performancegründen aber vielleicht lohnen könnte. Wobei das eher theoretische Überlegungen sind Premature optimization ist the root of all evil und so Andererseits erwarte ich von so grundlegenden Klassen wie Containern, dass sie auf Hinsicht auf Performance möglichst vernünftig implementiert sind und nicht unnötig Zeit verschwenden.
Eine andere Möglichkeit wäre wie gesagt ein Struct mit Funktionszeigern. Also, die virtual function pointer table von Hand nachbauen, dafür ist dein Iterator dann nur ein Objekt konstanter Größe.
Und wo ich das schreibe, fällt mir noch was ein. Wenn deine Implementierungsklasse keine Daten halten würde, sondern nur Paramter reinbekommen würde (die evtl. verändert werden) und der tree_iterator die Daten hält, könnte man den Zeiger auf die Implementierungsklasse einfach rumreichen und müsste das Objekt nicht mit new clonen.

[Cherup]

Mechanics schrieb:

Wenn deine Implementierungsklasse keine Daten halten würde, sondern nur Paramter reinbekommen würde (die evtl. verändert werden) und der tree_iterator die Daten hält, könnte man den Zeiger auf die Implementierungsklasse einfach rumreichen und müsste das Objekt nicht mit new clonen.

Die Idee finde ich richtig gut. Damit hätte man eine gute Kombination aus Performance und einer sauberen Implementierung.
Außerdem würden sich die Änderungen am Code in Grenzen halten
Ich habe wenig Lust die ganzen Iteratoren wieder zu entfernen nachdem ich da viele Stunden reingesteckt habe

[Cherup]

Die Änderungen am Iterator sind fertig.

Hier ein kleiner Changelog:

Iteratoren:
tree_iterator hält jetzt den Pointer auf den Node.
Pointer auf den Node werden an die iterator_impl-Klassen weitergereicht.
post-in/decrement sind aus den iterator_impl-Klasse geflogen
Umbennung der Operatoren in den iterator_impl-Klassen, nötig da operatoren keine Argumente annehmen.
Privater Konstruktor des tree_iterators angepasst.

Node:
Entsprechende Funktionen geben jetzt einen _Node* statt eines iterators zurück

tree:
Anpassungen in den Funktionen wegen der Änderung am tree_iterator.
tree hält jetzt shared_pointer auf die iterator_impl-Klassen.
shared_pointer auf die iterator_impl-Klassen werden nur an den tree_iterator gereicht, es werden keine neuen Instanzen mehr erzeugt.

Die Implementierung der Navigations-Funktionen des Iterators (Next(), Prev() usw) habe ich bewußt in der iterator_impl Klasse gelassen. Damit ist die Implementierung von dem tree_iterator getrennt. Es macht zwar nicht viel, aber es wirkt für mich sauberer und einheitlicher.

Den überarbeiteten Code findet ihr unter
http://pastebin.com/CKzYuD2S (treeContainer.h)
http://pastebin.com/7dfMRKe4 (treeContainer.cpp)

Wenn noch was auffällt bitte melden

Viele Grüße
Cherup

[Cherup]

Hallöchen nochmal,

mir ist bei der Benutzung tatsächlich noch was aufgefallen.
Und zwar folgendes:
Es kann ziemlich nervig werden, wenn man mehrere (mehr als 3 oder 4) neue Nodes in den Baum einfügen möchte, vor allem wenn es auch noch eine bestimmte Struktur in den anzuhänden Nodes geben soll.

Beispiel:
An einen Node sollen 3 Knoten angefügt werden, alle Nodes sollen 3 weitere Childnodes bekommen und der erste Childnode vom ersten ChildNode soll wieder 2 bekommen.
Das würde also so aussehen:

O
           /   |   \
          /    |    \
         O     O     O
        /|\   /|\   /|\
       O O O O O O O O O 
      / \
     O   O

Das macht zusammen 14 Knoten, die angefügt werden sollen, das sind mindestens 14 Befehle und 3 Iteratoren... Nicht sehr benutzerfreundlich.

Daher habe ich mir folgendes überlegt:
Da es ja die schöne Möglichkeit der Variadic Templates gibt nutze ich sie auch.
Ich schreibe also eine neue Funktion template<typename... T> createMultiple(), die beliebig viele Nodes erzeugen kann.
Schön und gut, aber ich will ja eine Struktur in den Nodes!
Da man keine zwei expansion packs an eine Funktion übergeben kann brauche ich dazu eine weitere interne öffentliche Klasse, die Strukturen speichern und die ich dann der createMultiple()-Funktion mit übergeben kann.
So weit so gut, wie übergebe ich der NodeStructure-Klasse jetzt die Struktur der Nodes? Wieder mit einer Variadic Template-Funktion und mit einem relativ einfachen Schema:
Man übergibt einfach die Anzahl der Nodes, die an jeden Node angehängt werden soll in der Reihenfolge der anzuhängenden Nodes.
Die erste Zahl steht also für die Anzahl der anzuhängen Nodes an den ParentNode, die 2. für die Anzahl der anzuhängen Nodes an den ersten ChildNode usw.

Für das obige Beispiel würde das dann so aussehen:
[3, 3, 2, 0, 0, 3, 0, 0, 0, 3, 0, 0, 0]

Gut, bei diesem Beispiel ist der Schreibaufwand noch realtiv gering, aber wenn ich z.B. 50 Nodes an ein einen der ChildNodes hängen möchte wirds unschön...
Auch da habe ich mir was überlegt. Man kann auch eine negative Zahl übergeben, die anzeigt an wieviele der nächsten Nodes kein Node angefügt werden soll. [..., -10,...] bedeutet also nichts anderes als 10 mal 0.
Die Zahlenfolge wäre dann z.b.
[3, 3, 2, -2, 3, -3, 3, -3]

Zusätzlich zu Zahlen sollen auch vector<int> und NodeStructures als Parameter möglich sein.

Die createMultiple()-Funktion würde also am Ende so aussehen:

template<typename... T> void createMultiple(const tree_iterator& pos, const NodeStructure& NStruc, T... Args);

Auch die "normale" createNode()-Funktion würde ich zu einem variadic template umschreiben, um mehrere Nodes auf einmal an einen Node anhängen zu können.

Jetzt die Frage:
Was haltet ihr davon? Ist das sinnvoll? Gibts Verbesserungen?

Cherup

[Mechanics]

Ich hätte bei deiner Anforderung erst einmal an eine Hilfsfunktion gedacht, die dann dreimal aufgerufen wird. Für die zweite Ebene evtl. noch eine Hilfsfunktion.

Ansonsten kann man bei solchen Strukturen schlecht sagen, wie sie dann später jemand benutzen will. Wäre so eine createMultiple Funktion wirklich flexibel und könnte man sie auch für andere Szenarien einsetzen? Ich hab keine Ahnung, so genau hab ichs auch nicht durchgelesen.
Eine Sequenz einzufügen finde ich aber erstmal nicht abwegig. Vielleicht als Iteratoren, damit man beliebige Container benutzen kann. Und die gibt dann einen "Tree Iterator" zurück, mit dem man über alle eingefügten Knoten drüberlaufen kann (ohne abzusteigen). Sowas könnte ich mir z.B. spontan vorstellen.

[Cherup]

Morgen,

Mechanics schrieb:

und könnte man sie auch für andere Szenarien einsetzen?

Das Szenario ist ganz allgemein: man möchte mehrere Knoten an einen vorhandenen Knoten anfügen und dabei auch gleichzeitig Kindknoten an die neuen Knoten anhängen.
Ich möchte die createMultiple-Funktion natürlich so implementieren, dass man beliebige Schemata an einen Node anfügen kann, das Beispiel war eben genau das, ein Beispiel.
Ich kann mir vorstellen, dass es öfter mal zu Szenarien kommt, in denen der Benutzer mehrere Nodes in einem bestimmten Muster einfügen möchte, z.B. um eine Speicherstruktur einzuhalten/darzustellen.
Simples Beispiel: Man liest eine XML-Datei ein und benutzt den Container um den Inhalt zu speichern/darzustellen. Dann könnte man mit der createMultiple den Inhalt eines ganzen Feldes nach dem gleichen Schema wie dem in der XML-Datei an einen Knoten anhängen.

Der Container eignet sich ja hervorragend dafür Strukturen darzustellen. Um bloß Werte zu speichern kann man auch einen schlichten vectorboost::any benutzen.
Ich nutze den Container momentan für genau so etwas, ich halte darin alle Objekte eines Programms in einem bestimmten Schema. Und ein angenehmer Nebeneffekt: Das schreiben und lesen der Objekte bzw deren Werte in/aus einer Datei ist sehr viel einfacher geworden

Mechanics schrieb:

Eine Sequenz einzufügen finde ich aber erstmal nicht abwegig. Vielleicht als Iteratoren, damit man beliebige Container benutzen kann. Und die gibt dann einen "Tree Iterator" zurück, mit dem man über alle eingefügten Knoten drüberlaufen kann (ohne abzusteigen). Sowas könnte ich mir z.B. spontan vorstellen.

Erkläre mir bitte genauer was du mit beliebige Container meinst.
Wenn ich dich richtig verstehe meinst du damit, das man über eine Sequenz mehrere Knoten an zum Teil schon existierende Knoten anhängen kann. Interessanter Gedanke aber auch komplex in der Umsetzung. Das würde bedeuten, dass die Schema-Klasse sowohl die Iteratoren für die betreffenden Knoten enthält als auch die Schemata für die anzuhängenen Knoten.
Einen tree_iterator zurückzugeben finde ich unnötig. Wenn man an mehrere Knoten anhängt kann man nicht ausschließlich über die angefügten Knoten laufen (das würde bedeuten, das ich eine zusätzliche Struktur brauche, die mir die angefügten Knoten speichert und über die der iterator läuft, aus meiner Sicht absolut überflüssig, wann löschen und wo speichern?) und wenn man an nur einen Knoten anfügt hat man bereits einen Iterator zum entsprechenden Node. Sofern man nur über die Kinder eines Knotens laufen möchte ohne abzusteigen nimmt man halt einen ChildIterator, dafür ist er schließlich da

[Mechanics]

Cherup schrieb:

Erkläre mir bitte genauer was du mit beliebige Container meinst.

Vielleicht sowas:

vector<int> v{1, 2, 3};
treeContainer::tree tree;
treeContainer::iterator pos = tree.find(...);
treeContainer::iterator it = tree.insert(pos, v.cbegin(), v.cend());
while (it.valid())
{
 appendMoreChildren(it);
 ++it;
}

Weiß nicht genau, wie das bei dir von der Syntax aussehen würde. Jedenfalls eine Möglichkeit, aus einer beliebigen Datenquelle über Iteratoren Werte in den Baum einzufügen, die auf einer Ebene liegen. Und man bekommt einen Iterator zurück, mit dem man über die eingefügten Knoten drüberlaufen kann, um weitere Ebenen einzufügen.

[Cherup]

Hmmm,

das was du beschrieben hast kannst du doch auch so mit dem Baum machen?

vector<int> v{1, 2, 3};
treeContainer::tree tree;
treeContainer::iterator pos = tree.find(...);
for(auto vpos = v.cbegin(); vpos != v.cend(); ++vpos) tree.createNode(pos, *vpos);
treeContainer::iterator it = tree.begin(pos); //holt einen ChilIterator
while (it != tree.end(pos))
{
 appendMoreChildren(it);
 ++it;
}

Ist nur minimal mehr Aufwand. Sofern an dem Knoten schon Kinder hängen ist die Anpassung auch nicht weiter schwer, braucht nur eine zusätzliche Codezeile und etwas andere Schleifenparameter...
Dafür braucht man meiner Meinung nach keine eigene Container-Funktion.
Mir geht es ja darum komplexere Daten-Strukturen mit wenigen Befehlen einfügen zu können
Zugegeben, es ist nicht nötig, kann aber in manchen Situationen sehr praktisch sein. Ich habe mir eine Hilfsfunktion geschrieben, die genau das macht, so bin ich auch auf die Idee gekommen

Aber die Idee mit den Iteratoren finde ich an sich sehr gut und praktisch. Werd mal überlegen, wie man das machen oder kombinieren könnte...