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...
Binärbäume sind eine äußerst grundlegende Funktionalität und tatsächlich grundlegender als andere Container, da Typen wie std::map, std::multimap und std::set auf ihnen basieren. Da diese Typen auf ihnen basieren, würde man erwarten, dass der zugrunde liegende Typ freigelegt wird.
Ich glaube nicht, dass der OP nach einem binären Baum fragt, er fragt nach einem Baum zur Speicherung einer Hierarchie.
Nicht nur das, das Hinzufügen eines Baum-"Containers" zur STL würde bedeuten, viele viele neue Konzepte hinzuzufügen, zum Beispiel einen Baumnavigator (Generalisierung von Iterator).
Dieser sieht vielversprechend aus und scheint das zu sein, wonach du suchst: http://tree.phi-sci.com/
Meiner Meinung nach ein Auslassung. Aber ich denke, es gibt gute Gründe, warum kein Baumstruktur in der STL enthalten ist. Es steckt viel Logik in der Pflege eines Baumes, die am besten als Memberfunktionen des Basisklasse TreeNode Objekts geschrieben werden. Wenn TreeNode in einem STL-Header verpackt ist, wird es nur noch unübersichtlicher.
Zum Beispiel:
template
struct TreeNode
{
T* DATA ; // Daten vom Typ T, die in diesem TreeNode gespeichert werden sollen
vector< TreeNode* > Kinder ;
// Einfügelogik für den Fall, dass ein Einfügen angefordert wird.
// Kann an Kinder anhängen oder an eines der Kindknoten weiterleiten
void einfuegen( T* neueDaten ) ;
} ;
template
struct Baum
{
TreeNode* wurzel;
// BAUM-Ebene Funktionen
void leeren() { delete wurzel ; wurzel = 0; }
void einfuegen( T* daten ) { if(wurzel) wurzel->einfuegen(daten); }
} ;
Beim Lesen der Antworten hier sind die häufigsten Gründe genannt, dass man nicht durch den Baum iterieren kann oder dass der Baum nicht die ähnliche Schnittstelle wie andere STL-Behälter annimmt und man STL-Algorithmen mit einer solchen Baumstruktur nicht verwenden könnte.
Mit diesem Gedanken habe ich versucht, meine eigene Baumdatenstruktur zu entwerfen, die eine STL-ähnliche Schnittstelle bereitstellt und so weit wie möglich mit vorhandenen STL-Algorithmen verwendet werden kann.
Meine Idee war, dass der Baum auf den vorhandenen STL-Behältern basieren muss und dass er den Behälter nicht verbergen darf, damit er für die Verwendung mit STL-Algorithmen zugänglich ist.
Ein weiteres wichtiges Merkmal, das der Baum bieten muss, sind die Traversierungsiteratoren.
Hier ist, was ich entwickeln konnte: https://github.com/cppfw/utki/blob/master/src/utki/tree.hpp
Und hier sind die Tests: https://github.com/cppfw/utki/blob/master/tests/unit/src/tree.cpp
Aber du kannst sagen, ob BFS oder DFS der richtige Weg ist. Oder unterstütze beide. Oder alles andere, was du dir vorstellen kannst. Sag dem Benutzer einfach, was es ist.
Ein Baum könnte seinen eigenen benutzerdefinierten Iterator-Typ definieren, der alle Knoten in der Reihenfolge von einem "Extrem" zum anderen durchläuft (d.h. für jeden Binärbaum mit den Pfaden 0 & 1 könnte er einen Iterator anbieten, der von "allen 0en" zu "allen 1en" geht, und einen umgekehrten Iterator, der das Gegenteil tut; für einen Baum mit einer Tiefe von 3 und dem Startknoten s könnte er z.B. über die Knoten iterieren als s000, s00, s001, s0, s010, s01, s011, s, s100, s10, s101, s1, s110, s11, s111 ("linkster- zu rechtster"); er könnte auch ein Tiefentraversierungsmuster verwenden (s, s0, s1, s00, s01, s10, s11,
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.