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

[Cherup]

Danke für die Idee,

wenn ich es richtig verstehe entspricht die Funktionalität in etwa meinem ersten "Nutzungswunsch". Mittlerweile bin ich dazu übergegangen den Tree so allgemein wie möglich zu halten, so dass an jedem Knoten alle Werte angehängt werden können.
Das Zusammenhängen der Listen ist aber eine gute Idee, dadurch wird das iterieren vereinfacht.

Aber aktuell habe ich ein Problem mit den shared_pointern, das mich schier verzweifeln lässt.
Um einen neuen Knoten an einen Knoten anzuhängen rufe ich die appendNode()-Funktion des Knotens auf und übergebe einen zuvor erstellten Node*.
Ich möchte den Knoten nicht direkt in der Funktion konstruieren, damit ich die Möglichkeit habe Knoten innerhalb des Baums zu verschieben.

Die Funktion schaut so aus:

std::shared_ptr<Node> Node::appendNode(Node* node)
{
    std::shared_ptr<Node> tmp(node);

    //Überprüfen ob node an den gleichen Knoten angehängt werden soll
    if(hasChild(tmp)) 
    {
        //myChildren = vector mit den angehängten Knoten als shared_ptr
        myChildren.push_back(tmp); 
        if(node->getParent()) node->getParent()->remove(node); 
    }

    //von den alten Knoten lösen und an den neuen anhängen
    node->extract();
    node->setParent(this);

    if(!myFirstNode) myFirstNode = myLastNode = node;
    else
    {
        myLastNode->setNext(node);
        node->setPrev(myLastNode);
        myLastNode = node;
    }

    return tmp;
}

Ich habe eine menge damit rumgespielt um sie zum Laufen zu bekommen, daher ist sie alles andere als gut.

Mein Problem ist, das der anzuhängen Node (also node) nach der Funktion wieder zerstört wird. tmp gilt zwar nur für diese Funktion, aber zum einen füge ich ihn ja in den vector ein, zum anderen gebe ich ihn zurück.

Ich überlege zurzeit ernsthaft ob ich nicht den smart_ptr-Mist sein lasse und zu einem manuellen Speicher-Management übergehe, das wäre für mich einfacher
Es kann doch nicht so schwer sein mit smart-Pointern umzugehen...

schönen Tag
Cherup

[zussel]

Cherup schrieb:

Danke für die Idee,

wenn ich es richtig verstehe entspricht die Funktionalität in etwa meinem ersten "Nutzungswunsch". Mittlerweile bin ich dazu übergegangen den Tree so allgemein wie möglich zu halten, so dass an jedem Knoten alle Werte angehängt werden können.

Ok, dann benötigst Du also keinen sortierten Baum. Verstehe.

Cherup schrieb:

Das Zusammenhängen der Listen ist aber eine gute Idee, dadurch wird das iterieren vereinfacht.

In der Tat wird dies ziemlich einfach

Cherup schrieb:

Aber aktuell habe ich ein Problem mit den shared_pointern, das mich schier verzweifeln lässt.
...
Die Funktion schaut so aus:

std::shared_ptr<Node> Node::appendNode(Node* node)
{
    std::shared_ptr<Node> tmp(node);
    
    // ...
    return tmp;
}

Du erzeugst im Scope der Funktion einen std::shared_ptr . Dieser hat einen Referenz-Count von 1. Demnach zerstört er sein Objekt am Ende der Funktion - unabhängig wo Du Deinen Pointer noch ablegst. Ausschlaggebend ist der Referenz-Count des std::shared_ptr .

Du könntest:

- von aussen schon einen std::shared_ptr mit dem Node übergeben.
- in der Methode einen std::unique_ptr nutzen und am Ende [c]release()[\c] aufrufen.

Gruß
zussel

[Cherup]

Wußt ichs doch, dass es mit dem Scope zusammenhängt...
Das Problem bei der ersten Möglichkeit wäre doch wieder das gleiche? Sobald die aufrufende Funktion verlassen wird, wird der shared_ptr wieder zerstört...

Ich muss aus meiner Sicht irgendwie ein neues shared_ptr-Object erstellen und dauerhaft behalten können...

Himmel, ich möchte doch bloß meine Knoten mit einem shared_ptr wrappen, damit ich eine gute Garbage-Collecting-Funktionalität habe, dass das so schwer sein kann...

Bin grad echt frustriert...

[zussel]

Ich kenne jetzt Deine Speicherstruktur nicht, aber Du fügst offensichtlich immer den rohen Pointer ein: appendNode(Node *node) .

Jetzt sehe ich erst, dass Du da eine Prüfung hast, ob der neue Knoten Kindelemente hat. Hier hängst Du den std::shared_ptr an eine Liste/Vektor.

Cherup schrieb:

std::shared_ptr<Node> Node::appendNode(Node* node)
{
    std::shared_ptr<Node> tmp(node);
    
    //Überprüfen ob node an den gleichen Knoten angehängt werden soll
    if(hasChild(tmp)) 
    {
        //myChildren = vector mit den angehängten Knoten als shared_ptr
        myChildren.push_back(tmp); 
        if(node->getParent()) node->getParent()->remove(node); 
    }

Weiter unten linkst Du aber den rohen Pointer in eine Liste.

Cherup schrieb:

// ...
    if(!myFirstNode) myFirstNode = myLastNode = node;
    else
    {
        myLastNode->setNext(node);
        node->setPrev(myLastNode);
        myLastNode = node;
    }

    return tmp;
}

Das ist ziemlich inkonsistent! Arbeite immer auf dem shared_ptr der auch später in Deiner Struktur abgelegt wird.
Also: einmal shared_ptr immer shared_ptr . Anderfalls kann es, wie in Deinem Fall, zu Speicherfehlern kommen.

Gruß
zussel

[Cherup]

Das ist leider ein Missverständnis meines Funktionsnames.
Mit hasChild() überprüfe ich, ob der Knoten an den gleichen Parent-Knoten angehängt wird, z.B. wenn ich einen Kindknoten statt in der Mitte der Liste am Ende haben möchte. Die hasChild()-Funktion ist nur eine temporäre Funktion um was zu testen.
Der Grund dafür ist recht simpel: an meinem Root-Knoten ist das letzte Element immer ein End-Knoten, das dient der einfacheren Überprüfung, ob ich am Ende des Trees bin. Wenn ich einen Knoten in der Liste verschiebe, entspricht das in etwa einer swap()-Funktion.
Eine eigene swap()-Funktion hab ich aus purer Faulheit (noch) nicht implementiert.

Die Speicherstruktur ist relativ simpel, 5 rohe Pointer auf die umliegenden Knoten und ein vector<shared_ptr<Node>> mit den angehängten Knoten um den Besitz der Objekte festzulegen.
Wie ich gelernt habe dienen die smartpointer ja dazu, den Besitz festzulegen und zwei Objekte können sich nicht gegenseitig besitzen...

[Cherup]

So, ich bin immer noch nicht wirklich weiter...
Um das aktuelle Problem mal klar zu formulieren:

Ich möchte über eine Funktion eines Nodes einen neuen Kind-Knoten erstellen und als shared_ptr in einem vector des Knotens speichern.
Das Problem ist, dass der shared_ptr beim verlassen der Funktion wieder zerstört wird.

Wie kann ich also den shared_ptr dauerhaft behalten und wie übergebe ich ihn an andere Funktionen?

Dazu gibt es noch die Einschränkung, dass der shared-ptr nicht von ausserhalb übergeben werden darf.

Ich nutze zwei Node-Funktionen um einen Knoten anzuhängen:
appendNode(), in der ein übergebener Knoten an den Node angehängt wird und appendNewNode(), in der ein neuer Knoten konstruiert wird und an appendNode() übergeben wird.
Ich trenne die beiden Funktionen, damit ich die Möglichkeit habe Knoten innerhalb des Baums zu verschieben.

Die Lösung ist wahrscheinlich sehr einfach und ich seh den Wald vor lauter Bäumen nicht, aber ich verzweifel wirklich daran...

[;qwerty]

Cherup schrieb:

Wie ich gelernt habe dienen die smartpointer ja dazu, den Besitz festzulegen und zwei Objekte können sich nicht gegenseitig besitzen...

std::unique_ptr legt Besitz fest. Mit der Verwendung von shared_ptr drückst du aus, dass es keinen oder mehrere Besitzer gibt bzw. dass du dir darüber einfach noch keine Gedanken gemacht hast.

Ich möchte über eine Funktion eines Nodes einen neuen Kind-Knoten erstellen und als shared_ptr in einem vector des Knotens speichern.
Das Problem ist, dass der shared_ptr beim verlassen der Funktion wieder zerstört wird.

Das kann dir egal sein, solange das Objekt, auf das der shared_ptr zeigt, nicht zerstört wird. Und das wird nicht geschehen, wenn du eine Kopie von ihm in myChildren abgelegt hast. Wenn du aber den entsprechenden shared_ptr aus myChildren rauswirfst und keine anderen shared_ptr zu diesem Zeitpunkt existieren, ist der Node weg - dann musst du sicherstellen, dass keine rohen Zeiger mehr darauf existieren. Falls du genau damit Probleme hast, verwendest du wahrscheinlich rohe Zeiger an Stellen, wo das nicht angebracht ist.

Wie kann ich also den shared_ptr dauerhaft behalten und wie übergebe ich ihn an andere Funktionen?

Du kannst einen shared_ptr beliebig kopieren, per Referenz übergeben und moven.

[Cherup]

Ok, es scheint endlich zu funktionieren und ich hab keine Ahnung warum
Ich habe eigenlich nicht wirklich was geändert, aber trotzdem...
Nunja, was solls.

Ich werde jetzt erstmal den Code aufräumen und nach Optimierungs/Vereinfachungsmöglichkeiten suchen.
Sobald das fertig ist, werd ich den ganze Code nochmal posten und nach eurer Meinung fragen

Schönen Tag noch
Cherup

[Cherup]

Und wieder ist eine Frage aufgetaucht
Allerdings "nur" nach einer guten Implementierung.
Ich möchte die Nodes und die interne Arbeitsweise soweit wie möglich verstecken, das betrifft insbesondere die Nodes, damit da kein Unfug mit getrieben werden kann und eben die Iteratoren.

Ich habe einen tree-iterator, von dem alle anderen Iteratoren abgeleitet sind. Um auf die Nodes zuzugreifen habe ich den Operator ->, welcher mir einen Node* zurückgibt. Da das aus meiner Sicht aber relativ "gefährlich" ist (man kann die umliegenden Nodes über get-Methode bekommen), möchte ich die nach aussen sichtbaren Funktionen eben in den tree-iterator packen, bzw. sie werden von dort aus aufgerufen.

Ist das grundsätzlich eine sinnvolle Vorgehensweise oder gibt es bessere Konzepte um die Arbeitsweise zu verstecken?

Die privaten Iterator-Methoden würde ich in eine eigene "Implementation-Klasse" packen und mit einem unique-ptr darauf zeigen.

[Mechanics]

Cherup schrieb:

möchte ich die nach aussen sichtbaren Funktionen eben in den tree-iterator packen, bzw. sie werden von dort aus aufgerufen.

Ich würde sie eher in die "Tree" Klasse packen, die die Iteratoren als Parameter bekommt. z.B. addChild(iterator parent, T obj).

[Cherup]

Morgen,

ich habe endlich mal wieder etwas Zeit gefunden an dem Container weiterzuarbeiten.
Ich habe, wie vorgeschlagen die Funktionen in die tree-Klasse gepackt, bin aber auf ein kleines Hindernis gestoßen. Es ist an sich nur ein "Schönheitsproblem", aber trotzdem.

Die tree-Klasse hat zwei appendNode-Funktionen, eine als Template um neue Werte in den Baum zu stecken und eine, die als "Wert" einen tree-iterator annimmt.
Die 2. Funktion brauche ich, um schon vorhandene Nodes in den Baum einzufügen, z.B. um Nodes zu verschieben.

template<typename T> node_iterator appendNode(tree_iterator it, T value);
node_iterator appendNode(tree_iterator it, tree_iterator node);

Das Problem ist, dass immer nur die template-Funktion aufgerufen wird, das ist mir soweit auch klar.
Die Frage ist also, wie ich dem Compiler klar machen kann, dass die "normale" und nicht die template-Funktion aufgerufen werden soll.
Ich habe schon versucht, eine spezialisierte template-Funktion zu schreiben, aber ich bin da wohl zu blöd für. Mir werden dann immer für den halben Container Fehler geschmissen

Ich kann das natürlich beheben, indem ich die beiden Funktionen verschieden benenne, aber ich möchte das nicht

[SeppJ]

Cherup schrieb:

Das Problem ist, dass immer nur die template-Funktion aufgerufen wird, das ist mir soweit auch klar.
Die Frage ist also, wie ich dem Compiler klar machen kann, dass die "normale" und nicht die template-Funktion aufgerufen werden soll.

Das sollte eigentlich nicht passieren, sofern du die Funktion mit den passenden Argumenten (also 2x tree_iterator) aufrufst. Nicht-Templates haben Vorrang. Zeig mal ein konkretes Minimalbeispiel, das bis auf den besagten Fehler compilierbar ist.

Ich habe schon versucht, eine spezialisierte template-Funktion zu schreiben, aber ich bin da wohl zu blöd für.

Das ist auch eine ganz schlechte Idee, kein Wunder, dass das nicht funktioniert.
http://www.gotw.ca/publications/mill17.htm

Ich kann das natürlich beheben, indem ich die beiden Funktionen verschieden benenne, aber ich möchte das nicht

Ich weiß zwar nicht, was deine Funktionen genau machen, aber von den Argumenten her kommt es mir so vor, als ob die zwei sehr unterschiedliche Dinge tun.

[Cherup]

SeppJ schrieb:

Ich weiß zwar nicht, was deine Funktionen genau machen, aber von den Argumenten her kommt es mir so vor, als ob die zwei sehr unterschiedliche Dinge tun.

Nein, eigentlich nicht. Die Template-Funktion erstellt einen neuen Node mit dem übergebenen Wert und hängt sie an den Node, auf den der Iterator zeigt, an, die normale Funktion hängt nur den Node, auf den der zweite Iterator zeigt an den Node des ersten Iterators an.

Ich glaube, ich habe den "Fehler" gefunden. Der tree_iterator ist eine Basisklasse und soll an sich nie benutzt werden. Es wird nur mit abgeleiteten Iteratoren gearbeitet. Da die ja nicht direkt vom Typ tree-Iterator sind wird dann die template-funktion aufgerufen.
Fällt euch dazu eine Lösung ein? Möglichst eine, bei der ich nicht 8 Funktionen schreiben muss um jeden Iteratortyp abzudecken?

[SeppJ]

cherup schrieb:

Da die ja nicht direkt vom Typ tree-Iterator sind wird dann die template-funktion aufgerufen.
Fällt euch dazu eine Lösung ein? Möglichst eine, bei der ich nicht 8 Funktionen schreiben muss um jeden Iteratortyp abzudecken?

Du castest sie beim Aufruf auf tree_iterator.

cherup schrieb:

Nein, eigentlich nicht. Die Template-Funktion erstellt einen neuen Node mit dem übergebenen Wert und hängt sie an den Node, auf den der Iterator zeigt, an, die normale Funktion hängt nur den Node, auf den der zweite Iterator zeigt an den Node des ersten Iterators an.

Eben. Das kommt mir wie zwei grundverschiedene Dinge vor.

[Cherup]

SeppJ schrieb:

Du castest sie beim Aufruf auf tree_iterator.

Du meinst, wenn ich die Funktion von ausserhalb des Containers aufrufe? Das möchte ich eher ungern, das verkompliziert die Benutzung.

SeppJ schrieb:

Eben. Das kommt mir wie zwei grundverschiedene Dinge vor.

Im Grunde unterscheiden sich beide Funktionen nur in einer Zeile, nämlich der wie man den anzuhängenden Node bekommt.
Ok, in der template-Funktion wird der Iterator zum Zurückgeben beim Erstellen des Nodes erstellt , während die normale Funktion das beim return erledigt, aber sonst...

//Node.appendNode() gibt einen node_iterator zurück
 treeContainer::node_iterator treeContainer::tree::appendNode(tree_iterator it, tree_iterator node)
{
    it.myNode->appendNode(std::shared_ptr<Node>(node.myNode));
    if(it.myNode == myRoot.get()) it.myNode->appendNode(myEnd);
    return node_iterator(node);
}

template<typename T> treeContainer::node_iterator treeContainer::tree::appendNode(tree_iterator it, T value)
{   
    node_iterator ret = it.myNode->appendNode(std::make_shared<Node>(value));
    if(it.myNode == myRoot.get()) it.myNode->appendNode(myEnd);
    return ret;
}

[SeppJ]

Etwas bestehendes zu kopieren und etwas neu zu erzeugen sind für mich eben zwei verschiedene Dinge. Wenn du das nicht so siehst, nun, dann hast du eben ein Design wie du es hier zeigst.

Wie kann ich denn einen tree_iterator in deinem Container abspeichern?

[Cherup]

Du hast recht, es sind zwei verschiedene Dinge, das sehe ich auch so. Ich wollte eine einheitliche Funktion, mit der man neue oder bestehende Nodes an einen anderen anhängen kann. Der Benutzer soll einfach nicht mit Nodes hantieren können.

SeppJ schrieb:

Wie kann ich denn einen tree_iterator in deinem Container abspeichern?

Da hast du mich
An die Möglichkeit, dass jemand die Iteratoren in den Container packen möchte hatte ich nicht gedacht.

Nun denn, dann werd ich die normale appendNode-Funktion wohl in move umbenennen, das entspricht wohl eher der Funktionalität...

Damit sollte der Container auch ziemlich fertig sein. Nach dem Testen werde ich den Code hier mal zeigen. Ich würde mich über Verbesserungsvorschläge oder Hinweise freuen.
Es geht mir auch um den Programmierstil, ein guter Stil ist mir wichtig.

[Cherup]

Ok, es ist doch noch ein Problem aufgetaucht
Bei der (jetzt) move-Funktion soll ja ein Knoten an einen neuen angehängt werden. Dazu wird die appendNode() Funktion des neuen Parent-Knotens aufgerufen und ein shared_ptr auf den anzuhängenden Knoten übergeben.
In der Funktion wird der shared_ptr in den "Children"-Vector des neuen Parents eingefügt und aus dem alten gelöscht. Damit wird der Besitzer des Knotens festgelegt.
Das Problem ist nun, dass beim löschen aus dem Vector des alten Parents der Destructor des Nodes aufgerufen wird und damit das Datenobjekt flöten geht. Die restlichen Daten (also die Pointer auf die umliegenden Nodes) bleiben bestehen.
Was mich dabei irritiert ist der use_count von 3 des shared_ptr. Nach meinem Verständnis dürfte der Destructor also nicht aufgerufen werden.

Das Ganze mal als Code:

//move() von tree
treeContainer::node_iterator treeContainer::tree::move(tree_iterator it, tree_iterator node)
{
    it.myNode->appendNode(std::shared_ptr<Node>(node.myNode)); //Typ myNode: tree::Node*
    if(it.myNode == myRoot.get()) it.myNode->appendNode(myEnd);
    return node_iterator(node);
}

//appendNode() von Node
treeContainer::node_iterator treeContainer::tree::Node::appendNode(std::shared_ptr<Node> node)
{
    //myChildren: std::vector<std::shared_ptr<Node>>
    myChildren.push_back(node);
    if(node->getParent()) node->getParent()->erase(node); //

    (...)

    return node_iterator(node.get());
}

//erase() von Node
void treeContainer::tree::Node::erase(std::shared_ptr<Node> node)
{
    for(auto it = myChildren.begin(); it != myChildren.end(); ++it)
    {
        if(it->get() == node.get())
        {
            myChildren.erase(it); //node wird gelöscht obwohl use_count = 3
            return;
        }
    }
}

Ich hoffe ihr könnt mir da weiterhelfen und das Verhalten erlären...
Für mich sieht das Verhalten so aus, als ob da mit verschiedenen Objekten gearbeitet wird, die Speicheradressen der Node-Objekte sind aber gleich...

[SeppJ]

Das wird mit 6 Seiten Threadhistorie etwas schwer nachzuvollziehen. Kannst du das auf ein minimales Beispiel herunterbrechen, das man im Debugger nachvollziehen kann?

[Cherup]

SeppJ schrieb:

Kannst du das auf ein minimales Beispiel herunterbrechen, das man im Debugger nachvollziehen kann?

Das ist relativ schwer, weil der Container recht umfangreich ist. Ich kann aber den Code mal veröffentlichen (siehe unten).

Ich habe versucht ein Minimalbeispiel zu schreiben, das relativ ähnlich ist (hoffe ich). Da wird der "Node" zwar nicht gelöscht, der use_count der Holder-Klasse (speichert den Wert) steht aber auf 0 und er existiert trotzdem

Hier das Beispiel:

//Main:
#include "testclass.h"

int main(int argc, char *argv[])
{
    testclass* myTestClass = new testclass();
    return 0;
}

//testclass.h:
#include <memory>
#include <map>
#include <vector>

using namespace std;

class testclass
{
private:
    class node;
public:
    testclass();
    vector<std::shared_ptr<node>> myNodes;

private:
    class node{
        public:
            node(int value) { myHolder = make_shared<holder>(value); }
            ~node(){}
            int getValue() { return myHolder->getValue(); }
            void appendNode(shared_ptr<node> newNode) { myNodeNodes.push_back(newNode); }
            void eraseNode(shared_ptr<node> eraNode)
            {
                for(uint i=0; i<myNodeNodes.size(); i++)
                    if(myNodeNodes[i].get() == eraNode.get())
                        myNodeNodes.erase(myNodeNodes.begin()+i);
            }
            shared_ptr<node> getNode(int index){ return myNodeNodes[index]; }

        private:
            class holder
            {
            public:
                holder(int value) : myValue(value) {}
                ~holder(){}
                int getValue() {return myValue;}
            private:
                int myValue;
            };

            std::shared_ptr<holder> myHolder;
            vector<std::shared_ptr<node>> myNodeNodes;
    };
};

//testclass.cpp:
#include "testclass.h"

testclass::testclass()
{
    for(uint i=0; i<3; i++){
        myNodes.push_back(make_shared<node>(i));
        for(uint j=1; j<6; j++){
            myNodes[i]->appendNode(make_shared<node>(j+(i*5)));
        }
    }
    node* temp = myNodes[0]->getNode(4).get();
    myNodes[2]->appendNode(shared_ptr<node>(temp));
    myNodes[0]->eraseNode(myNodes[0]->getNode(4));

    return;
}

Ich weiß, der Stil ist furchtbar, aber sollte halt schnell gehen
Eine Ausgabe muss selbstgeschrieben werden. Ich arbeite mit dem QT-Creator und da läuft das halt nur über Qdebug...

Den Code für den Container findet ihr unter:
treeContainer.h: http://pastebin.com/rCTgEE7t
treeContainer.cpp: http://pastebin.com/1eq7wuX3
Ist aber größtenteils noch unkommentiert und an den "Problem"-Funktionen etwas unschön.

Schönen Samstag
Cherup