Binärbaum +STL oder nicht

Hi,
ich muß einen Binärbaum implementieren.
Ich würde ihn ganz normal implementieren, da es wie schon ab und an besprochen keine binären Bäume in der stl gibt.
Gibt es Verfahren, wei man sich aus der STL binärbäume zusammen baut, oder
würdet ihr ihn kurtz so schreiben.
Gruß

knivil

std::set wird mit einem Binaerbaum implementiert.

Nexus

Wenn es dir um die Datenstruktur selbst geht: Im C++-Magazin gibt es zwei Artikel zu Bäumen, vielleicht helfen die dir auch weiter.

Danke für eure Antworten.
Ich habe mich dazu entschieden den Baum selbst zu implementieren, da ich gerne in jedem Fall einen Baum hätte und die implementierung der Maps von der STl nicht dtandardisiert sind.
Mir ist nun wichtig, dass mein Baum eine Ordnung erhält welche nicht festgelegt ist. Dabei würde ich entweder:
-Funktor
-Funktionspointer
-operator < als friend überladen
Das Letztere scheidet für mich nahe zu aus, da ich, um zu vermeiden dass eine
standardmäßige, vom Benutzer der klasse nicht vorgegebene Ordnungsstruktur existiert, die klasse virtuell machen würde. In diesem Fall ist mir das zu langsam, zumal der operator häufig gebraucht werden wird.
Ich kann mich nicht zwischen Funktionspointer und Funktor entscheiden.
Welche vor-nachteile weisen denn die beiden auf ??
(Funktor kann man inline machen)
(Referenzieren ist verdammt flot)
Gruß

Sebastian Pizer

Was willst Du denn mit dem Baum machen? Also, was soll er für Funktionalität bieten? Speziell im Vergleich zu std::set und std::map.

camper

Ich würde vermuten - ohne es konkret überprüft zu haben - dass die heutige Compilergeneration mit Funktionszeigern als Templateargument genausogut umgehen kann wie mit Funktoren. Das gleich zu implementieren ist schließlich nicht sehr furchtbar schwierig und die Problematik seit 10 Jahren bekannt.

Die Schwierigkeit bei der Verwendung von Funktionszeigern besteht darin, dass man den genauen Funktionstyp angeben muss. Grundsätzlich wäre so etwas möglich:

template <typename T, typename Comp>
class binary_tree { ... };

template <typename T, bool(*f)(const T&,const T&)>
class binary_tree_func1 : private binary_tree<T,functorize1<f> > { ... };

template <typename T, typename Func, Func* f>
class binary_tree_func2 : private binary_tree<T,functorize2<F,f> > { ... };

(mit einem kleinen Hilfstemplate, dass unseren Funktionspointer in einen Funktor umwandelt. Die Problematik ist hier deutlich zu sehen: die betreffende Funktion muss eine ganz bestimmte Signatur haben, oder aber wir müssen den Funktionstyp explizit angeben, was unbequem ist.

Hier offenbart sich eine Schwäche (mangelnde Orthogonalität) bei der Spezifikation von Templatparametern: während ein typename X jeden beliebigen Typ umfasst, gibt es keine Möglichkeit, einen non-type Templateparameter beliebigen Typs zu spezifizieren (den tatsächlichen Typ könnte man dann durch partielle Spezialisierung oder decltype bestimmen). Vermutlich stehe ich mit dieser Ansicht aber ziemlich allein da, jedenfalls ist mir kein enstrepechender Vorschlag für C++0x bekannt.

Von der funktionalität her wäre es genau das richtige, std::map oder std::set zu nehmen. Da hast du Recht.
Aber die Implementierung der beiden ist nicht vorgeschrieben. Mir ist es damit zu heikel, dass ev. mal eine Implementation etwas langsamer ist.
(Das kann mangels erfahrung sein, aber wenn mans schon liest, dass
die Implementierung willkürlich ist......)
Wenn ich std::map oder std::set nehme, kann ich dort ein explizites Ordnungskriterium angeben ??
(Ich muß liniensegmente verglcihen, die M dimensional sein können. Also N Punkte, mit M freiheitsgraden, welch miteinander verbunden sind.)
Gruß

@camper
Die Antwort muß ich mir ersteinmal zu gemüte führen. Aber ehrzlichen Dank, das schaut sehr interessant aus.

@Sebastian
Habe schon selbst nachgeschaut. Ich schreibe oft während dem Lesen der Antwroten meine Bedenken hier rein.
Denke Set und map würden funktionieren.
Aber Camper hat tolle Sachen gezeigt

Gruß

unskilled

AlexXXx schrieb:

Aber die Implementierung der beiden ist nicht vorgeschrieben. Mir ist es damit zu heikel, dass ev. mal eine Implementation etwas langsamer ist.

Die Komlexität ist im Standard vorgeschrieben...
So hat bsp. std::map::operator[] immer log(n)

bb

Okay dann werde ich die map nehmen. oder set, wird sich zeigen
Bin so oder so faul heute ggg
Gruß

knivil

Wenn ich std::map oder std::set nehme, kann ich dort ein explizites Ordnungskriterium angeben ??

Etwas mehr Eigeninitiative bitte! Schau selbst erstmal nach, es gibt genug Referenzen im Netz.

AlexXXx schrieb:

@Sebastian
Habe schon selbst nachgeschaut. ....
Gruß

Nach dem abschicken wars mir schon pleinlich. Tschuldigung.
Aber meine Motivation rennt nackig mit nem cocktail über die wiese *ggg*
Gruß

Die fast fanatisch wirkende Eigeninitiative, welche sich dadurch äußert, einen Binärbeum selbst implementieren zu wollen, grenzt doch fast schon an Dummheit
Gruß

Nexus

camper schrieb:

Hier offenbart sich eine Schwäche (mangelnde Orthogonalität) bei der Spezifikation von Templatparametern: während ein typename X jeden beliebigen Typ umfasst, gibt es keine Möglichkeit, einen non-type Templateparameter beliebigen Typs zu spezifizieren (den tatsächlichen Typ könnte man dann durch partielle Spezialisierung oder decltype bestimmen). Vermutlich stehe ich mit dieser Ansicht aber ziemlich allein da, jedenfalls ist mir kein enstrepechender Vorschlag für C++0x bekannt.

Hm, wenn ich dich richtig verstehe, kann dieser Mangel teilweise (bei integralen Konstanten, da diese als statische Member für den Compiler sichtbar definiert werden können) durch eine Indirektion behoben werden. Mir scheint zumindest dieser Ansatz noch naheliegend:

// statt...
template <exprname N>  // exprname im Gegensatz zu typename für Nicht-Typ-Parameter
class MyClass
{
    // mache was mit N
};

// ...hat man eine Indirektion
template <typename T>
class MyClass
{
    // mache was mit T::value (T besitzt Nicht-Typ-Member value)
    // In C++98 von Vorteil, da T auch ein typedef haben kann -> kein decltype nötig
};

Die Initialisierung von static const -Membern in der Klasse soll meines Wissens im neuen Standard nicht auf integrale Typen beschränkt bleiben, wodurch weitere Fälle durch diesen Workaround abgedeckt werden können.