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

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

  • C

    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

    0
  • C

    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.

    0
  • M

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

    0
  • C

    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 😃

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

    0
  • C

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

    0
  • Mod

    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.

    0
  • C

    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;
}
    0
  • Mod

    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?

    0
  • C

    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.

    0
  • C

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

    0
  • Mod

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

    0
  • C

    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

    0
  • C

    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

    0
  • M

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

    Die Zeilen werden sich wahrscheinlich beißen.

    0
  • C

    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?

    0
  • M

    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.

    0
  • C

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

    0
  • M

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

    0
  • C

    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

    0
Anmelden zum Antworten