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



  • Der Name "shared_ptr" rührt daher, dass sich jedermann das Eigentum, also das angezeigte Objekt, teilt. Darum gibt es keine Besitzerschaft in dem Sinne von bspw. unique_ptr. Dass Objekte gelöscht werden, obwohl noch ein shared_ptr drauf zeigt, ist eigentlich unmöglich. Da musst Du mit dem bloßen Zeiger (ptr.get()) noch etwas schlimmes gemacht haben.



  • Möglicher typischer Fehler: einen shared_ptr vom this Objekt erstellen, ohne enable_shared_from_this (was ich an sich auch möglichst vermeiden würde).



  • Danke,
    Ich hab ja gesagt, dass ich die shared_ptr misshandle 😃

    Mit den Zeigern mache ich an sich nichts, ich frage nur einmal ab, ab der Zeiger auf this zeigt.
    Aber ich habe den typischen Fehler gemacht, ich habe mehrmals einen shared-ptr vom this Object erstellt und übergeben.
    Ich muss ja this an den anzuhängenden Node übergeben um damit den Parent-Pointer zu setzen. Wie mache ich das am besten, this übergeben und im Node mit make_shared oder einem shared_ptr-Konstruktor dem Parent-Pointer zuweisen?



  • Bei Baumstrukturen bietet sich eher ein unique_ptr für die Kinder an. Es ist ja klar, wem das Objekt gehört. Das ist einer der Gründe, warum ich ursprünglich vorgeschlagen habe, Iteratoren zu benutzen und Treenodes zu verstecken. Der Benutzer soll damit nicht rumpfuschen können, dann ist die Speicherverwaltung einfacher.



  • Du meinst, jeder Node hat die unique-ptr seiner Kinder?
    Das hat zwar den Vorteil des Speichermanagments, ist aber meiner Meinung nach deutlich schwieriger zu implementieren (wenn ich die Unique_ptr richtig verstehe).
    Zum einen braucht man, um über die Kinder zu iterieren den Parent-Node, zum anderen ist eine Iteration über den Baum mittels einer Tiefensuche schwierig. Man muss ja wieder zum Parent-Node zurückkommen, d.h. man braucht eine Art rekursiven Iterator. Und man hat meiner Meinung nach recht viel Verwaltungsoverhead im Node.
    Aktuell hab ich die Kinder als doppelt verkettete Liste realisiert.
    Auf die Nodes selbst kann auch nur mit einem Iterator zugegriffen werden.



  • Gibt verschiedene Möglichkeiten, einen Baum zu implementieren, und keine ist für alle möglichen Fälle optimal. Ich dachte eigentlich, du hättest die Kinder als shared_ptr implementiert, deswegen der Vorschlag mit dem unique_ptr. So ganz versteh ich aber nicht, was du schreibst. Wenn du einen Parent brauchst, kannst du den einfach als Zeiger speichern. Ich seh da jetzt nicht mehr Verwaltungsoverhead. Wo brauchst du einen shared_ptr, wenn du eine doppelt verkettete Liste hast?



  • Morgen,
    ich nutze shared Pointer im Wesentlichen, damit ich die Nodes nicht manuel löschen muss.
    Aber ich hab das Konzept der Smart-Pointer noch nicht wirklich verstanden, ich hoffe jetzt ist es klarer...
    Ich werde jetzt erstmal die Nodes so umbauen, das jeder in einem vector<unique_ptr> sein Kinder speichert und die verkettung zwischen den Nodes über normale Pointer läuft...



  • Habe gerade diesen Thread entdeckt. Echt interessantes Thema. Eine ähnliche Problematik hatte ich auch für mein Projekt zu lösen. Ich habe mir folgende Lösung erarbeitet:

    Ich nutze einen N-Baum mit den Typ Informatiomen. Dadurch kann ich Objekthierarchien abbilden. Jeder Typ Knoten besitzt eine doppelt verkettete Liste mit Elementen von exakt dem Typ den dieser Knoten repräsentiert.

    Die Einzelnen verketteten Listen hängen jedoch zusammen, sodass ich _eine_ lange verkettete Liste habe, die sich um alle Typ-Knoten legt.

    Auf diese Weise habe ich einen Container, der seine Elemente hierarchisch ablegen kann. Das einfügen geht ziemlich fix und der Zugriff ist ebenfalls recht schnell. Zum Beispiel kann ich auf einen Schlag auf alle Elemente inklusive der hierarchisch untergeordneten Elemente zugreifen.

    Wollte Dir das nur mal so als Idee beschreiben. Vielleicht ist eine ähnliche Architektur auch eine Variante für Dein Problem.



  • 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



  • 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



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



  • 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



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



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



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



  • 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



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



  • 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).



  • 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 😃


  • Mod

    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.


Anmelden zum Antworten