Warum bietet der C++ STL keine "Baum"-Container und was ist stattdessen am besten zu verwenden?
Ich möchte eine Hierarchie von Objekten als Baum speichern, anstatt einen Baum als Leistungsverbesserung zu verwenden...
Es gibt zwei Gründe, warum du einen Baum verwenden könntest:
Du möchtest das Problem mit einer baumartigen Struktur abbilden:
Dafür haben wir die Boost Graph Library
Oder du möchtest einen Container mit baumähnlichen Zugriffseigenschaften: Dafür haben wir
std::map (und std::multimap)std::set (und std::multiset)Grundsätzlich sind die Eigenschaften dieser beiden Container so, dass sie praktisch mit Bäumen implementiert werden müssen (obwohl dies eigentlich keine Anforderung ist).
Siehe auch diese Frage: C-Baumimplementierung
Es gibt viele Gründe, einen Baum zu verwenden, auch wenn dies die häufigsten sind. Am häufigsten bedeutet nicht gleich alle.
Eine dritte Hauptursache, einen Baum haben zu wollen, ist eine immer sortierte Liste mit schnellen Einfügungen/Entfernungen, aber dafür gibt es std:multiset.
Wie können wir eine Karte für eine Baumdatenstruktur verwenden, wenn wir die Tiefe des Baumes nicht kennen?
Wahrscheinlich aus dem gleichen Grund, aus dem es keinen Baumcontainer in Boost gibt. Es gibt viele Möglichkeiten, einen solchen Container zu implementieren, und es gibt keinen guten Weg, um alle zufriedenzustellen, die ihn nutzen würden.
Einige zu berücksichtigende Probleme:
Letztendlich besteht das Problem darin, dass ein Baumcontainer, der für jeden nützlich genug wäre, für die meisten Benutzer zu schwerwiegend wäre. Wenn Sie nach etwas Leistungsstarkem suchen, ist die Boost Graph Library im Wesentlichen eine Übermenge dessen, wofür eine Baum-Bibliothek verwendet werden könnte.
Hier sind einige andere generische Baum-Implementierungen:
"...kein guter Weg, um alle zufriedenzustellen..." Mit Ausnahme dessen, dass stl::map, stl::multimap und stl::set basierend auf stl's rb_tree sind, sollte es genauso viele Fälle zufriedenstellen wie diese grundlegenden Typen.
Angesichts der Tatsache, dass es keinen Weg gibt, die Kinder eines Knotens einer std::map abzurufen, würde ich diese nicht als Baumcontainer bezeichnen. Es handelt sich um assoziative Container, die häufig als Bäume implementiert sind. Ein großer Unterschied.
Ich bin einverstanden mit Mooing Duck, wie würdest du eine Breitensuche auf einer std::map implementieren? Es wird wahnsinnig teuer sein
"Ich möchte eine Hierarchie von Objekten als Baum speichern"
C++11 ist gekommen und gegangen und sie haben immer noch nicht gesehen, dass es notwendig wäre, einen std::tree bereitzustellen, obwohl die Idee aufkam (siehe hier). Vielleicht haben sie das deshalb nicht hinzugefügt, weil es trivial einfach ist, Ihren eigenen Baum auf Basis der vorhandenen Container zu erstellen. Zum Beispiel...
template< typename T >
struct tree_node
{
T t;
std::vector children;
};Ein einfacher Durchlauf würde Rekursion verwenden...
template< typename T >
void tree_node::walk_depth_first() const
{
cout<`
Wenn Sie eine Hierarchie beibehalten möchten und sie mit STL-Algorithmen funktionieren soll, können die Dinge kompliziert werden. Sie könnten Ihre eigenen Iteratoren erstellen und einige Kompatibilität erreichen, aber viele der Algorithmen ergeben einfach keinen Sinn für eine Hierarchie (zum Beispiel alles, was die Reihenfolge eines Bereichs ändert). Selbst das Definieren eines Bereichs innerhalb einer Hierarchie könnte eine komplizierte Angelegenheit sein.
`
Wenn das Projekt es erlauben kann, die Kinder eines tree_node zu sortieren, dann kann die Verwendung eines std::set<> anstelle eines std::vector<> und das Hinzufügen eines operator<() zum tree_node-Objekt die 'Such'-Leistung eines 'T'-ähnlichen Objekts erheblich verbessern.
Es stellte sich heraus, dass sie faul waren und tatsächlich dein erstes Beispiel als undefiniertes Verhalten gemacht haben.
@Mehrdad: Ich habe mich endlich entschieden, nach den Details hinter Ihrem Kommentar hier zu fragen.
Die Philosophie der STL ist, dass Sie einen Container basierend auf Garantien auswählen und nicht basierend darauf, wie der Container implementiert ist. Zum Beispiel kann Ihre Wahl des Containers auf einem Bedarf nach schnellen Suchvorgängen beruhen. Ihnen ist es egal, ob der Container als unidirektionale Liste implementiert ist - solange die Suche sehr schnell ist, wären Sie zufrieden. Das liegt daran, dass Sie die internen Strukturen ohnehin nicht berühren, sondern Iteratoren oder Methoden für den Zugriff verwenden. Ihr Code ist nicht an die Implementierung des Containers, sondern daran gebunden, wie schnell er ist, ob er eine festgelegte Reihenfolge hat oder ob er effizient im Speicher ist und so weiter.
Ich glaube nicht, dass er über Container-Implementierungen spricht, er spricht über einen tatsächlichen Baumcontainer selbst.
@MooingDuck Ich denke, was wilhelmtell meint, ist, dass die C++-Standardbibliothek Container nicht nach ihrer zugrunde liegenden Datenstruktur definiert; sie definiert Container nur nach ihrer Schnittstelle und beobachtbaren Eigenschaften wie asymptotischer Leistung. Wenn man darüber nachdenkt, ist ein Baum nicht wirklich ein Container (wie wir sie kennen). Sie haben nicht einmal ein einfaches end() und begin(), mit dem man durch alle Elemente iterieren kann, usw.
@JordanMelo: Quatsch auf allen Punkten. Es ist eine Sache, die Objekte enthält. Es ist sehr trivial, es so zu entwerfen, dass es ein begin() und end() und bidirektionale Iterator hat, um damit zu iterieren. Jeder Container hat unterschiedliche Eigenschaften. Es wäre nützlich, wenn man zusätzlich auch Baum-Eigenschaften haben könnte. Sollte ziemlich einfach sein.
Wenn Sie nach einer RB-Baum-Implementierung suchen, könnte stl_tree.h auch für Sie geeignet sein.
Seltsamerweise ist dies die einzige Antwort, die tatsächlich die ursprüngliche Frage beantwortet.
Unter Berücksichtigung dessen, dass er eine "Hierarchie" will, scheint es sicher anzunehmen, dass alles mit "Ausgleich" die falsche Antwort ist.
"Dies ist eine interne Header-Datei, die von anderen Bibliotheks-Headern eingeschlossen wird. Sie sollten nicht versuchen, sie direkt zu verwenden."
CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.
9 Stimmen
Ich brauche einen Baum, um eine hierarchische Darstellung zu speichern.
29 Stimmen
Ich bin bei dem Typen, der die "richtigen" Antworten heruntergevotet hat, was anscheinend lautet: "Bäume sind nutzlos". Es gibt wichtige, wenn auch wenig bekannte, Verwendungszwecke von Bäumen.
0 Stimmen
Ich denke, der Grund ist trivial - niemand hat es bisher in die Standardbibliothek implementiert. Es ist wie die Standardbibliothek hatte bisher keine
std::unordered_mapundstd::unordered_setbis vor kurzem. Und davor gab es überhaupt keine STL-Behälter in der Standardbibliothek.3 Stimmen
Meine Gedanken (ohne jemals den relevanten Standard gelesen zu haben, daher handelt es sich hierbei um einen Kommentar und nicht um eine Antwort) sind, dass die STL sich nicht um spezifische Datenstrukturen kümmert, sondern um Spezifikationen hinsichtlich der Komplexität und welche Operationen unterstützt werden. Die verwendete zugrunde liegende Struktur kann zwischen Implementierungen und/oder Zielarchitekturen variieren, solange sie den Spezifikationen entspricht. Ich bin ziemlich sicher, dass
std::mapundstd::setin jeder Implementierung einen Baum verwenden werden, aber sie müssen es nicht tun, wenn eine nicht-baumartige Struktur auch den Spezifikationen entspricht.