nullptr auf Stack und 0xCCCCCCCC

SeppJ

In Zeile 43 kopierst du den parent-Node und zerstörst das Original. Irgendwie habe ich dieses Szenario befürchtet, als du in deinem anderem Thread gefragt hast, was make_shared genau macht. Die vorsichtigen Antworten dort hast du als Freibrief genommen, wild und verständnislos mit Pointern rum zu spielen.

camper

node<T> *parent_
und
std::vector<std::shared_ptr<node<T>>> children
passen soweiso nicht zusammen, da die offensichtliche Invariante
this->children[x]->parent == this
nicht gelten kann, sobald ein Node von mehreren Knoten bessesen wird. Eigentlich sollten ja alle shared_ptr auf daselbe Objekt äquivalent sein, aber offenbar sind dann manche gleicher als andere.

Finnegan

happystudent schrieb:

Hallo,

ok bezüglich des unique_ptr's war ich mir noch unsicher, wegen der Diskussion im oben verlinkten Thread (da gab es ja noch keinen so richtigen Konsens).

tissie schrieb:
Der Fehler liegt bei
children.back()->parent_ = this;
, weil der node die Adresse ändert, wenn er kopiert wird.
Ok... aber ich kopiere doch nur den Pointer und nicht das node objekt selbst? Also das führt dann auch zu einer Adress-Änderung?

node verändert nicht seine Adresse, das ist etwas unglücklich formuliert. Was tissie wahrscheinlich meint, ist dass der Kindknoten, den du in make_a_node() zum Elternknoten n hinzufügst, mit der Anweisung return n in einen neuen Knoten (mit anderer Adresse) kopiert wird, und somit dessen parent-Pointer auf nicht mehr auf seinen tatsächlichen Elternknoten verweist sondern auf den mittlerweile nicht mehr existierenden (temporären) Elternknoten n (Stichw. Dangling Pointer).

Mögliche Lösungen wären z.B. ein Copy-Konstruktor, der (rekursiv) die parent-Pointer aller Kindknoten anpasst, oder (meines erachtens sinnvoller) eine make_a_node() -Funktion die einen (Smart-)Pointer zurückgibt, anstatt den gesamten Baum, der an n hängt zu kopieren.

happystudent schrieb:

tissie schrieb:

- Mache dir die Besitz-Abhängigkeiten klar. Stelle sicher, dass node nur als unique_ptr erstellt werden kann (also mach den Konstruktor privat). Dann kann die Adresse nicht mehr geändert werden.

Äh, aber wie soll ich das Objekt dann erstellen wenn der Konstruktor privat ist? Und parent_ ist doch gar kein unique_ptr sondern ein roher Pointer, das geht dann folglich auch nicht?

Vermutlich will tissie auf so etwas wie eine Factory-Methode hinaus. Wenn du z.B. make_a_node() z.B. zu einer statischen (public-) Methode von node machst (oder make_a_node() als friend deklarierst), kann diese immer noch Knoten erstellen, da sie als Methode von node den privaten Konstruktor aufrufen darf. Das würde ich allerdings auf den ersten Blick nur dann als sinnvoll erachten, wenn du sicherstellen willst, dass neue Knoten nur mit make_a_node() erzeugt werden können (z.B. wenn wie tissie erwähnt hat, Knoten nur als unique_ptr erstellt werden sollen).

Was die Wahl der Smart-Pointer angeht ("Besitzverhältnisse"): Shared Pointer machen eigentlich erst dann Sinn, wenn meherere Objekte "Besitzer" eines anderen sein können (shared ownership). Ich weiss nicht genau, wie du deine Baumstruktur geplant hast, da dein node jedoch nur einen parent-Pointer hat, kann ein Knoten höchstens einen Elternknoten haben - oder anders: Es kann für jeden Knoten nur einen einzigen anderen Knoten geben, der auf diesen verweist. Es liegt also eigentlich kein "shared ownership" vor, weshalb es auch Unique-Pointer tun, die weniger Overhead haben. Als Grundstruktur empfiehlt sich also eher so etwas in diese Richtung:

struct node
{
    node* parent;
    vector<unique_ptr<node>> children;

    ...

    unique_ptr<node> make_a_node()
    {
        unique_ptr<node> n(new node());
        n->add_child(1);
        return n;
    }

    private:
        node() {}
};

Mir fällt natürlich auch ein Anwendungsfall ein, bei dem die Shared Pointer trotzdem Sinn machen:

Du möchtest z.B. Unterbäume deines Baums in andere Datenstrukturen "einhängen" und die Lebenszeit dieser Datenstrukturen kann die des Baums überdauern. In diesem Fall lohnt es sich sogar eventuell, den parent-Pointer zu einem Weak-Pointer zu machen, damit sich z.B. erkennen lässt, wenn Elternknoten nicht mehr existieren.

Finnegan

happystudent

Hallo,

Danke schonmal für die ausführliche Antwort, ich habs jetzt soweit mit unique_ptr hinbekommen und es funktioniert auch (endlich) wie es soll.

Eine Frage hätte ich allerdings noch. Ich hab jetzt den vorgeschlagenen Weg einer statischen, erzeugenden Member-Funktion gewählt, nach diesem Prinzip:

template <typename T>
class node
{
	// ...
public:
	static std::unique_ptr<node<T>> make(T const &data)
	{
		return std::unique_ptr<node<T>>(new node<T>(data));
	}

	// ...
};

Das kappt jetzt auch soweit. Allerdings hab ich versucht den Aufruf von new durch make_unique zu ersetzen, nämlich so:

return std::make_unique<node<T>>(data); // In Zeile 8 oben

was ja genauso funktionieren sollte, oder?

Auf jeden Fall geht das nicht, da ich eine Compile-Fehlermeldung erhalte: "cannot access private member declared in class 'nodestd::string'".

was wohl daran liegt dass der Konstruktor jetzt privat ist... Aber wie soll man das umgehen?

Finnegan

happystudent schrieb:

was ja genauso funktionieren sollte, oder?

Auf jeden Fall geht das nicht, da ich eine Compile-Fehlermeldung erhalte: "cannot access private member declared in class 'nodestd::string'".

was wohl daran liegt dass der Konstruktor jetzt privat ist... Aber wie soll man das umgehen?

Ja, das Problem habe ich auch schon gehabt. Es gibt dafür eine portable Lösung, die allerdings zu etwas umständlicherem Code führt. Ich fasse zuerst nochmal kurz die Motivation hinter dem aktuellen Design zusammen, damit du dir nochmal überlegen kannst, ob du make und/oder make_unique wirklich benötigst:

Warum privater Konstruktor?

Der Konstruktor ist privat um sicherzustellen, dass Instanzen von node ausschließlich durch einen Aufruf von make erstellt werden können. Gründe hierfür können z.B. sein:
- Du möchtest sicherstellen, dass node -Instanzen nur als unique/shared-Pointer erstellt werden können (ist bei dir möglicherweise der Fall).
- Das Erstellen einer neuen Instanz erfordert zusätzlichen Code (z.B. irgendeine Form von Buchführung), der nicht im Konstruktor ausgeführt werden kann/soll.
- Singleton-Entwurfsmuster, bei dem sichergestellt weren soll, dass immer nur eine Instanz der Klasse existiert.

Warum make_unique ?

Im Gegensatz zu make_shared , bei dem der Kontrollblock mit dem Referenzzähler und das Objekt direkt nebeneinander im Speicher erzeugt werden (cache-freundlich), hat make_unique keinen zu erwartenden Performancevorteil.
Allerdings hat make_unique den Vorteil "exception-safe" zu sein, wenn innerhalb eines Ausdrucks an verschiedenen Stellen Exceptions geworfen werden.
Beispiel:

funktion(unique_ptr<T>(new T()), funktionDieExceptionWerfenKann());

Hier kann der Code in folgender Reihenfolge auswertet werden:

new T()
funktionDieExceptionWerfenKann()
unique_ptr<T>(T*)
Wenn nun funktionDieExceptionWerfenKann() eine Exception wirft, dann wird der Speicher, der durch new T() reserviert wurde nicht freigegeben, da der reservierte Speicher noch nicht dem unique_ptr zugewiesen wurde (Speicherleck). Mit make_unique kann das nicht passieren.

Bei deinem derzeitigen Code kann das allerdings nicht auftreten, da hier ausschließlich der Konstruktor von T werfen könnte → du kannst vorerst auf make_unique verzichten.

Wenn du dennoch make_unique verwenden möchtest, ist eine Möglichkeit, den Konstruktor zwar public zu machen, ihm aber ein Argument zu geben, dessen Typ wiederum einen privaten Konstruktor hat, der mithilfe einer friend-Deklaration von make aufgerufen werden darf:

template <typename T>
class node
{
    public:
        static std::unique_ptr<node> make(T const& data)
        {
            return std::make_unique<node>(data, construct_via_make());
        }

        class construct_via_make
        {
            // Statische make-Methode ist "friend", darf also 
            // den Konstruktor construct_via_make() aufrufen.
            friend std::unique_ptr<node> node::make(T const&);
            // Konstruktor ist private (default für "class").
            construct_via_make() {}
        };

        // Konstruktor ist zwar public, erfordert aber als
        // zweites Argument eine Instanz von construct_via_make,
        // die nur von make() erstellt werden darf (friend).
        node(T const& data, construct_via_make const&) {}
};

Das ist zwar ein wenig umständlich, aber dafür eine portable Lösung. Man könnte zwar auch naiv erst einmal versuchen make_unique als friend von node zu deklarieren, es gibt allerdings keine Garantie dafür das make_unique auch tatsächlich diejenige Funktion ist, die den Konstruktor von node aufruft (das hängt von der Implementation der Standardbibliothek ab und kann für jeden Compiler anders sein).

Wegen der zusätzlich erzeugten temporären Instanz von `construct_via_make

, die inmake` erzeugt wird, würde ich mir übrigens performance-technisch keine Sorgen machen. Jeder Compiler, der etwas auf sich hält wird so etwas komplett rausoptimieren.

Gruss,
Finnegan

happystudent

Ok, alles klar. Mir war nicht bewusst dass make_unique anders als make_shared keinen weiteren Performancevorteil mit sich bringt.

Da es dann hier ja "egal" ist ob make_unique oder direkt der Konstruktor verwendet wird, werd ich dann bei der Lösung mit new bleiben. Danke auf jeden Fall für die Erläuterungen

Au man, so viel Trouble wegen einer kleinen Baumklasse, da sind ja rohe Pointer ein Segen gegen, aber hier werden ja immer die "einfachen" Smartpointer in den Himmel gehoben.

Wenn ich solche Threads lese(und davon gibt es viele) dann vergeht mir schon wieder die Lust am C++ lernen.

theta

CppTrouble schrieb:

Au man, so viel Trouble wegen einer kleinen Baumklasse, da sind ja rohe Pointer ein Segen gegen, aber hier werden ja immer die "einfachen" Smartpointer in den Himmel gehoben.

Och ich denke, dass Leute die Probleme im Umgang mit Smart-Pointern haben, auch auf Probleme mit rohen Pointern stossen werden.

Skym0sh0

CppTrouble schrieb:

Au man, so viel Trouble wegen einer kleinen Baumklasse, da sind ja rohe Pointer ein Segen gegen, aber hier werden ja immer die "einfachen" Smartpointer in den Himmel gehoben.

Wenn ich solche Threads lese(und davon gibt es viele) dann vergeht mir schon wieder die Lust am C++ lernen.

Wie theta schon sagte, Probleme gibts auch bei rohen Pointer.

Der Unterschied ist jedoch, dass man bei rohen Pointer die Fehler meist einfach nicht sieht oder bemerkt. Denn ein vergessenes delete, zum Beispiel, wird von niemandem gemeldet und davon abhängig können ganz andere Probleme im kanal untergehen ohne sie jemals zu sehen.

Nathan

CppTrouble schrieb:

Au man, so viel Trouble wegen einer kleinen Baumklasse, da sind ja rohe Pointer ein Segen gegen, aber hier werden ja immer die "einfachen" Smartpointer in den Himmel gehoben.

Wenn man nicht weiß, wie man mit einem Hammer umgehen kann und Nägel immer mit einem Stein in die Wand haut, der ist darin so gut, dass er keinen Sinn sieht, bessere Werkzeuge wie Hämmer (ist das der Plural?) zu verwenden.
Wenn man jedoch einmal den Umgang mit einem Hammer gelernt hat, ist man darin wesentlich schneller.

Man muss natürlich lernen mit seinen Werkzeugen umzugehen, bevor man sie schnell einsetzen kann. Und wenn man es kann, sind Smartpointer deutlich einfacher.