Dlaczego C++ STL nie dostarcza żadnych kontenerów "tree"?

Prawdopodobnie z tego samego powodu, że nie ma kontenera drzewa w boost. Istnieje wiele sposobów na wdrożenie takiego kontenera i nie ma dobrego sposobu, aby zadowolić wszystkich, którzy by go używali.

Niektóre kwestie do rozważenia:
- Czy liczba dzieci dla węzła jest stała czy zmienna?
- Ile na węzeł? - czyli, czy potrzebne są wskaźniki rodzica, rodzeństwa itp.
- Jakie algorytmy podać? - różne Iteratory, algorytmy wyszukiwania itp.

In the end, the problem polega na tym, że kontener drzewa, który byłby wystarczająco przydatny dla wszystkich, byłby zbyt ciężki, aby zadowolić większość osób, które go używają. Jeśli szukasz czegoś potężnego, Boost Graph Library {[9] } jest zasadniczo supersetem tego, do czego można użyć biblioteki drzewa.

Oto kilka innych implementacji drzewa generycznego:
- Drzewo Kaspra Peetersa.hh
- Adobe ' s forest
- core:: tree

Filozofia STL polega na tym, że wybieramy kontener w oparciu o gwarancje, a nie w oparciu o sposób implementacji kontenera. Na przykład, wybór kontenera może być oparty na potrzebie szybkiego wyszukiwania. Kontener może być zaimplementowany jako jednokierunkowa lista - o ile wyszukiwanie jest bardzo szybkie, będziesz zadowolony. To dlatego, że nie dotykasz i tak wewnętrznych, używasz iteratorów lub funkcji Członkowskich do dostępu. Twój kod nie jest związany z kontener jest zaimplementowany, ale do tego, jak szybko jest, lub czy ma stałe i zdefiniowane porządkowanie, lub czy jest wydajny na przestrzeni, i tak dalej.

"chcę przechowywać hierarchię obiektów jako drzewo"

C++11 pojawił się i zniknął, a oni nadal nie widzieli potrzeby dostarczania std::tree, chociaż pomysł pojawił się (zobacz tutaj). Być może powodem, dla którego tego nie dodali, jest trywialnie łatwe budowanie własnych na istniejących kontenerach. Na przykład...

template< typename T >
struct tree_node
   {
   T t;
   std::vector<tree_node> children;
   };

Prosty traversal użyłby rekursji...

template< typename T >
void tree_node<T>::walk_depth_first() const
   {
   cout<<t;
   for ( auto & n: children ) n.walk_depth_first();
   }

Jeśli chcesz utrzymać hierarchię i chcesz, aby praca z algorytmami STL , wtedy sprawy mogą się skomplikować. Możesz zbudować własne Iteratory i osiągnąć pewną kompatybilność, jednak wiele algorytmów po prostu nie ma sensu dla hierarchii(na przykład wszystko, co zmienia kolejność zakresu). Nawet zdefiniowanie zakresu w hierarchii może być brudnym biznesem.

Jeśli szukasz implementacji RB-tree, to stl_tree.h może być również odpowiednie dla Ciebie.

Mapa std:: jest oparta na drzewie red black tree . Możesz również użyć innych kontenerów , aby pomóc ci zaimplementować własne typy drzew.

W pewnym sensie std:: map jest drzewem (wymagane jest posiadanie takich samych parametrów wydajności jak zrównoważone drzewo binarne), ale nie ujawnia innych funkcji drzewa. Prawdopodobna argumentacja za nieuwzględnieniem prawdziwej struktury danych drzewa była prawdopodobnie tylko kwestią nieuwzględnienia wszystkiego w stl. Stl może być postrzegany jako framework do wykorzystania w implementacji własnych algorytmów i struktur danych.

Ogólnie rzecz biorąc, jeśli istnieje podstawowa funkcjonalność biblioteki, którą chcesz, to Nie w stl, poprawką jest spojrzenie na BOOST .

W przeciwnym razie istnieje Grupa bibliotek out tam , w zależności od potrzeb Twojego drzewa.

Wszystkie kontenery STL są zewnętrznie reprezentowane jako "sekwencje" z jednym mechanizmem iteracji. Drzewa nie podążają za tym idiomem.

Ponieważ STL nie jest biblioteką "wszystko". Zawiera, w zasadzie, Minimalne struktury potrzebne do budowania rzeczy.

Ten wygląda obiecująco i wydaje się być tym, czego szukasz: http://tree.phi-sci.com/

IMO, pominięcie. Ale myślę, że jest dobry powód, aby nie włączać struktury drzewa w STL. Istnieje wiele logiki w utrzymywaniu drzewa, które najlepiej jest zapisać jako funkcje member do obiektu base TreeNode . Gdy TreeNode jest zawinięty w nagłówek STL, staje się on po prostu bardziej messier.

Na przykład:

template <typename T>
struct TreeNode
{
  T* DATA ; // data of type T to be stored at this TreeNode

  vector< TreeNode<T>* > children ;

  // insertion logic for if an insert is asked of me.
  // may append to children, or may pass off to one of the child nodes
  void insert( T* newData ) ;

} ;

template <typename T>
struct Tree
{
  TreeNode<T>* root;

  // TREE LEVEL functions
  void clear() { delete root ; root=0; }

  void insert( T* data ) { if(root)root->insert(data); } 
} ;

Myślę, że jest kilka powodów, dla których nie ma drzew stl. Przede wszystkim drzewa są formą rekurencyjnej struktury danych, która podobnie jak kontener (lista, wektor, zbiór) ma bardzo różną strukturę, co utrudnia prawidłowe wybory. Są również bardzo łatwe do zbudowania w podstawowej formie za pomocą STL.

Skończone drzewo korzeniowe może być traktowane jako kontener, który ma wartość lub ładunek, powiedzmy instancję klasy A i ewentualnie pusty zbiór korzeniowych (sub) drzew; drzewa to puste subtrees są jak liście.

template<class A>
struct unordered_tree : std::set<unordered_tree>, A
{};

template<class A>
struct b_tree : std::vector<b_tree>, A
{};

template<class A>
struct planar_tree : std::list<planar_tree>, A
{};

Trzeba trochę pomyśleć o projekcie iteratora itp. i które operacje produktowe i współproduktowe pozwalają definiować i być wydajne pomiędzy drzewami - a oryginalny stl musi być dobrze napisany - tak, aby pusty kontener zestawu, wektora lub listy był naprawdę pusty dla dowolnego ładunku w domyślnym przypadku.

Jednak oprócz drzew istnieją również "drzewa współbieżne"; drzewa przede wszystkim mają właściwość, że jeśli usuniesz korzeń, usuniesz wszystko.

Rozważ Iteratory na drzewie, prawdopodobnie będą one realizowane jako prosty stos iteratorów, do węzła i do jego rodzica ... aż do korzenia.

template<class TREE>
struct node_iterator : std::stack<TREE::iterator>{
operator*() {return *back();}
...};

Możesz jednak mieć tyle, ile chcesz; zbiorczo tworzą one "drzewo", ale gdzie wszystkie strzałki płyną w kierunku korzenia, to wspólne drzewo może iterować, choć Iteratory w kierunku trywialnego iteratora i korzenia; jednak nie może być poruszane w poprzek lub w dół (inne Iteratory nie są mu znane), ani zespół iteratorów nie może być usunięty, z wyjątkiem trzymania go w dłoni. śledzenie wszystkich instancji.

Drzewa są niezwykle przydatne, mają dużą strukturę, co sprawia, że uzyskanie definitywnie poprawnego podejścia jest poważnym wyzwaniem. Moim zdaniem dlatego nie są one implementowane w STL. Co więcej, w przeszłości widziałem, jak ludzie stają się religijni i uważają, że idea typu kontenera zawierającego instancje własnego typu jest wyzwaniem - ale muszą się z tym zmierzyć - to jest to, co reprezentuje typ drzewa - jest to węzeł zawierający prawdopodobnie pusty zbiór (mniejszych) drzew. Obecny język pozwala na to bez problemu, zapewniając domyślny konstruktor dla container<B> nie przydziela miejsca na stercie (ani nigdzie indziej) dla B, itd.

Wszystkie kontenery STL mogą być używane z iteratorami. Nie możesz mieć iteratora ani drzewa a, ponieważ nie masz "jednej właściwej" drogi przechodzącej przez drzewo.