Dynamische mehrfachverkettete Liste?

Student83

Hallo, gibt es in C++ so etwas wie eine dynamische mehrfachverkettete Liste, also eine Kette in der jeder Knoten mehrere ChildNodes haben kann? Problem: Die Anzahl der ChildNodes müsste allerdings zur Laufzeit variierbar sein, steht also beim Start der Anwendung noch nicht fest. Ich müsste also Child-Knoten hinzufügen (nicht einfügen) oder Löschen können.
Das i-Tüpfelchen wäre jetzt noch einzelne Knoten (über einen Index) direkt ansprechen zu können, ohne jeden Teilknoten nach einem Element absuchen zu müssen.

Falls das so nicht möglich ist, wie könnte ich diese Funktion anders angehen?

cirion

in einer doppelt verketteten liste hat jeder knoten höchstens einen vorgänger und höchstens einen nachfolger. mehrere nachfolger gibt es nur in einem baum bzw. graph. insofern werde ich aus deinen anforderungen nicht so ganz schlau.

ru,
cirion

DaRpH

Klar gibts das

typedef std::list<std::pair<DeineKlasse*, std::list< DeineKlasse* > > > mehrfachliste;

Einfach 2 schachteln. Für mehr ebenen müsstest du in deine Klasse die jeweiligen ChildNodes einfach als std::list reinmachen.

cirion

das wäre eine interpretation dessen, was er schrieb.

ru,
cirion

Student83

Die Interpretation war richtig ;). Mit Mehrfachverkettung meinte ich in eine Richtung, also nicht, dass der zweite Zeiger auf den Parentnode zeigt. War etwas irreführend ausgedrückt.

Das mit der "list<MyClass> Children" werde ich mal ausprobieren. Habe gesehen, dass damit sogar "foreach" funktioniert.

cirion

Student83 schrieb:

Die Interpretation war richtig ;). Mit Mehrfachverkettung meinte ich in eine Richtung, also nicht, dass der zweite Zeiger auf den Parentnode zeigt. War etwas irreführend ausgedrückt.

du bist dir darüber im klaren, dass es sich bei dem genannten typedef-konstrukt um eine liste von listen handelt (also das listen-äquivalent eines zweidimensionalen arrays)? sprich, jede innere liste ist zusammen mit dem gepairten zeiger (einzelner) knoten der äußeren liste? mehrfache kinder gibts dabei nicht.

was er unter "für mehr ebenen" schrieb, führt letztlich zu einem baum, und ist unabhängig von dem typedef-konstrukt.

ru,
cirion

Nexus

Student83 schrieb:

Das mit der "list<MyClass> Children" werde ich mal ausprobieren. Habe gesehen, dass damit sogar "foreach" funktioniert.

Es gibt in C++ noch kein foreach . Was es gibt, sind Makros wie BOOST_FOREACH , die prinzipiell das selbe tun, oder der STL-Algorithmus std::for_each() .

Student83

@cirion
Jupp, ist mir klar. Das hatte ich schon vermutet, dass dies so nicht geht.

@Nexus
Mit "foreach" meinte ich den STL-Algorithmus, darum in Anführungszeichen.