Dlaczego C ++ STL nie zapewnia żadnych kontenerów „drzewiastych”?

Dlaczego C ++ STL nie zapewnia żadnych kontenerów „drzewiastych” i czego najlepiej użyć zamiast tego?

Chcę przechowywać hierarchię obiektów jako drzewo, zamiast używać drzewa jako ulepszenia wydajności ...

Istnieją dwa powody, dla których warto użyć drzewa:

Chcesz odwzorować problem za pomocą struktury drzewiastej:
Do tego mamy bibliotekę grafów pomocniczych

Lub chcesz kontener, który ma cechy dostępu podobne do drzewa. Do tego mamy

• std::map(i std::multimap)
• std::set(i std::multiset)

Zasadniczo cechy tych dwóch kontenerów są takie, że praktycznie muszą zostać zaimplementowane przy użyciu drzew (choć tak naprawdę nie jest to wymagane).

Zobacz także to pytanie: Implementacja drzewa C.

Prawdopodobnie z tego samego powodu, dla którego nie ma kontenera drzewa doładowania. Istnieje wiele sposobów na wdrożenie takiego kontenera i nie ma dobrego sposobu na zaspokojenie wszystkich, którzy by z niego korzystali.

Niektóre kwestie do rozważenia:

• Czy liczba dzieci w węźle jest stała czy zmienna?
• Ile narzutów na węzeł? - tzn. czy potrzebujesz wskaźników nadrzędnych, wskaźników rodzeństwa itp.
• Jakie algorytmy podać? - różne iteratory, algorytmy wyszukiwania itp.

Ostatecznie problemem jest to, że pojemnik na drzewo, który byłby wystarczająco użyteczny dla wszystkich, byłby zbyt ciężki, aby zadowolić większość osób, które z niego korzystają. Jeśli szukasz czegoś potężnego, Boost Graph Library jest w zasadzie nadzbiorem tego, do czego biblioteka drzewek mogłaby zostać użyta.

Oto kilka innych ogólnych implementacji drzewa:

• Drzewo Kaspera Peetersa. Hh
• Las Adobe
• rdzeń :: drzewo

Filozofia STL polega na tym, że wybierasz kontener na podstawie gwarancji, a nie na podstawie sposobu implementacji kontenera. Na przykład wybór kontenera może być oparty na potrzebie szybkiego wyszukiwania. Dla ciebie wszystko jedno: kontener może być zaimplementowany jako lista jednokierunkowa - dopóki wyszukiwanie jest bardzo szybkie, będziesz szczęśliwy. To dlatego, że i tak nie dotykasz elementów wewnętrznych, używasz iteratorów lub funkcji członkowskich w celu uzyskania dostępu. Twój kod nie jest związany z tym, jak kontener jest zaimplementowany, ale z tym, jak szybki jest, czy ma ustaloną i zdefiniowaną kolejność, czy jest efektywny pod względem miejsca i tak dalej.

„Chcę przechowywać hierarchię obiektów jako drzewo”

C ++ 11 przyszedł i zniknął i nadal nie widzieli potrzeby zapewnienia std::tree, chociaż pomysł się pojawił (patrz tutaj ). Być może powodem, dla którego tego nie dodali, jest to, że łatwo jest zbudować własny na istniejących kontenerach. Na przykład...

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

Proste przejście wymagałoby rekurencji ...

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 działała z algorytmami STL , sprawy mogą się skomplikować. Możesz zbudować własne iteratory i osiągnąć pewną zgodność, 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ć bałaganem.

Jeśli szukasz implementacji drzewa RB, plik stl_tree.h może być odpowiedni również dla Ciebie.

std :: map jest oparty na czerwonym, czarnym drzewie . Możesz także użyć innych pojemników, aby pomóc Ci wdrożyć własne typy drzew.

W pewnym sensie, std :: map jest drzewem (wymagane jest, aby mieć takie same parametry wydajności jak zrównoważone drzewo binarne), ale nie ujawnia innych funkcjonalności drzewa. Prawdopodobne uzasadnienie nieuwzględnienia prawdziwej struktury danych drzewa było prawdopodobnie tylko kwestią niewłączenia wszystkiego do STL. STL może być postrzegany jako środowisko do implementacji własnych algorytmów i struktur danych.

Ogólnie rzecz biorąc, jeśli potrzebujesz podstawowej funkcji biblioteki, której nie ma w STL, poprawka polega na spojrzeniu na BOOST .

W przeciwnym razie istnieje grono z bibliotekami się tam , w zależności od potrzeb drzewa.

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

Ponieważ STL nie jest biblioteką „wszystkiego”. Zawiera zasadniczo 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 uwzględniać struktury drzewa w STL. W utrzymywaniu drzewa jest dużo logiki, którą najlepiej zapisywać jako funkcje składowe w TreeNodeobiekcie podstawowym . Kiedy TreeNodejest zawinięty w nagłówek STL, robi się coraz bardziej bałagan.

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 istnieje 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, zestaw), ma bardzo różną drobną strukturę, co utrudnia prawidłowe wybory. Są również bardzo łatwe do zbudowania w podstawowej formie za pomocą STL.

Skończone zrootowane drzewo może być traktowane jako pojemnik, który ma wartość lub ładunek, powiedzmy, przykład klasy A i ewentualnie pustej kolekcji ukorzenionych (pod) drzew; drzewa z pustą kolekcją poddrzewa są uważane za 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 się trochę zastanowić nad projektem iteratora itp. Oraz nad tym, które operacje produktu i produktu towarzyszącego pozwalają definiować i być wydajne między drzewami - a oryginalny STL musi być dobrze napisany - aby pusty kontener, wektor lub lista była naprawdę pozbawiony ładunku w domyślnym przypadku.

Drzewa odgrywają istotną rolę w wielu strukturach matematycznych (zobacz klasyczne artykuły Butchera, Grossmana i Larsena; także w artykułach Connesa i Kriemera przykłady ich łączenia i sposobu ich wyliczania). Błędem jest myśleć, że ich rolą jest po prostu ułatwianie niektórych innych operacji. Ułatwiają one raczej te zadania ze względu na ich podstawową rolę jako struktury danych.

Jednak oprócz drzew istnieją również „współ-drzewa”; przede wszystkim drzewa mają tę właściwość, że usunięcie korzenia powoduje usunięcie wszystkiego.

Rozważ iteratory na drzewie, prawdopodobnie byłyby one realizowane jako zwykły stos iteratorów, do węzła i do jego elementu nadrzędnego ... aż do katalogu głównego.

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

Możesz jednak mieć tyle, ile chcesz; wspólnie tworzą „drzewo”, ale tam, gdzie wszystkie strzały płyną w kierunku korzenia, to wspólne drzewo może być iterowane przez iteratory w kierunku trywialnego iteratora i korzenia; jednak nie można nawigować w poprzek lub w dół (inne iteratory nie są mu znane) ani też zespół iteratorów nie może zostać usunięty, chyba że śledzi wszystkie instancje.

Drzewa są niezwykle przydatne, mają dużą strukturę, co stanowi poważne wyzwanie, aby uzyskać zdecydowanie poprawne podejście. Moim zdaniem dlatego nie są one zaimplementowane w STL. Co więcej, w przeszłości widziałem ludzi religijnych i pomysł na typ kontenera zawierającego instancje własnego typu stanowił wyzwanie - ale muszą stawić temu czoła - to reprezentuje typ drzewa - jest to węzeł zawierający ewentualnie pusta kolekcja (mniejszych) drzew. Obecny język pozwala na to bez żadnych wątpliwości, zapewniając domyślny konstruktorcontainer<B> nie przydziela miejsca na stercie (lub gdziekolwiek indziej) na Bitp.

Z jednej strony byłbym zadowolony, gdyby to w dobrej formie znalazło się w normie.

Czytając tutaj odpowiedzi, najczęściej wymienianymi powodami są to, że nie można iterować przez drzewo lub drzewo nie przyjmuje podobnego interfejsu do innych kontenerów STL i nie można używać algorytmów STL o takiej strukturze drzewa.

Mając to na uwadze, próbowałem zaprojektować własną strukturę danych drzewa, która zapewni interfejs podobny do STL i będzie w jak największym stopniu możliwa do wykorzystania z istniejącymi algorytmami STL.

Mój pomysł polegał na tym, że drzewo musi być oparte na istniejących kontenerach STL i nie może ukrywać kontenera, aby można go było używać z algorytmami STL.

Inną ważną cechą, którą drzewo musi zapewnić, są iteratory ruchu.

Oto, co udało mi się wymyślić: https://github.com/igagis/utki/blob/master/src/utki/tree.hpp

A oto testy: https://github.com/igagis/utki/blob/master/tests/tree/tests.cpp

Wszystkie kontenery STL mogą być używane z iteratorami. Nie możesz mieć iteratora na drzewie, ponieważ nie masz „jednej właściwej” drogi, aby przejść przez drzewo.