[c++] Perché il C ++ STL non fornisce contenitori "ad albero"?



5 Answers

Probabilmente per la stessa ragione per cui non ci sono contenitori di alberi in boost. Esistono molti modi per implementare un contenitore del genere e non esiste un buon modo per soddisfare tutti coloro che lo utilizzano.

Alcuni aspetti da considerare:
- Il numero di figli per un nodo è fisso o variabile?
- Quanto overhead per nodo? - cioè, hai bisogno di indicatori genitore, puntatori fraterni, ecc.
- Quali algoritmi fornire? - diversi iteratori, algoritmi di ricerca, ecc.

Alla fine, il problema è che un contenitore di alberi che sarebbe abbastanza utile per tutti, sarebbe troppo pesante per soddisfare la maggior parte delle persone che lo utilizzano. Se stai cercando qualcosa di potente, Boost Graph Library è essenzialmente un superset di ciò che una libreria di alberi potrebbe essere utilizzata.

Ecco alcune altre implementazioni generiche degli alberi:
- Albero di Kasper Peeters
- La foresta di Adobe
- core::tree

Question

Perché il C ++ STL non fornisce contenitori "ad albero" e quale invece è la cosa migliore da usare?

Voglio memorizzare una gerarchia di oggetti come un albero, piuttosto che usare un albero come un miglioramento delle prestazioni ...




"Voglio memorizzare una gerarchia di oggetti come un albero"

C ++ 11 è arrivato e se n'è andato e non hanno ancora visto la necessità di fornire un std::tree sebbene l'idea sia venuta fuori (vedi here ). Forse la ragione per cui non hanno aggiunto questo è che è banalmente facile crearne di propri in cima ai contenitori esistenti. Per esempio...

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

Una semplice traversata ricorrerebbe alla ricorsione ...

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

Se si desidera mantenere una gerarchia e si desidera che funzioni con gli algoritmi STL , le cose potrebbero complicarsi. È possibile creare i propri iteratori e ottenere una certa compatibilità, tuttavia molti algoritmi semplicemente non hanno alcun senso per una gerarchia (qualsiasi cosa che modifichi l'ordine di un intervallo, ad esempio). Anche definire un intervallo all'interno di una gerarchia potrebbe essere un affare disordinato.




Penso che ci siano diversi motivi per cui non ci sono alberi STL. In primo luogo, gli alberi sono una forma di struttura dati ricorsiva che, come un contenitore (elenco, vettore, insieme), ha una struttura fine molto diversa che rende difficili le scelte corrette. Sono anche molto facili da costruire in forma base usando l'STL.

Un albero con radice finita può essere pensato come un contenitore che ha un valore o un carico utile, diciamo un'istanza di una classe A e, eventualmente, una raccolta vuota di alberi (sotto) radicati; alberi che vuoti di sottoalberi sono come foglie.

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
{};

Si deve pensare un po 'al design degli iteratori, ecc. E quali operazioni di prodotto e co-prodotto si possono definire ed essere efficienti tra gli alberi - e lo stl originale deve essere ben scritto - così che il set vuoto, il vettore o il contenitore dell'elenco sia veramente vuoto di qualsiasi payload nel caso predefinito.

Gli alberi svolgono un ruolo essenziale in molte strutture matematiche (vedi le carte classiche di Butcher, Grossman e Larsen, anche le carte di Connes e Kriemer per esempi di esse possono essere unite, e come sono usate per enumerare). Non è corretto pensare che il loro ruolo sia semplicemente quello di facilitare alcune altre operazioni. Piuttosto facilitano tali compiti a causa del loro ruolo fondamentale come struttura dei dati.

Tuttavia, oltre agli alberi ci sono anche "co-alberi"; soprattutto gli alberi hanno la proprietà che se si cancella la radice si cancella tutto.

Considera gli iteratori sull'albero, probabilmente sarebbero realizzati come una semplice pila di iteratori, su un nodo e verso il suo genitore, ... fino alla radice.

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

Tuttavia, puoi averne quante ne vuoi; collettivamente formano un "albero" ma dove tutte le frecce scorrono nella direzione verso la radice, questo co-albero può essere iterato attraverso iteratori verso l'iteratore e la radice triviali; tuttavia non può essere spostato su o giù (gli altri iteratori non sono noti) né l'insieme di iteratori può essere cancellato, tranne tenendo traccia di tutte le istanze.

Gli alberi sono incredibilmente utili, hanno un sacco di struttura, questo rende una seria sfida per ottenere l'approccio definitivamente corretto. A mio avviso, questo è il motivo per cui non sono implementati nell'STL. Inoltre, in passato, ho visto persone diventare religiose e trovare l'idea di un tipo di contenitore contenente istanze del suo stesso tipo impegnative - ma devono affrontarlo - è ciò che rappresenta un tipo di albero - è un nodo che contiene un raccolta vuota di alberi (più piccoli). La lingua corrente lo consente senza alcuna sfida, fornendo il costruttore predefinito per il container<B> non alloca spazio sull'heap (o altrove) per un B , ecc.

Io per primo sarei lieto se questo, in una buona forma, trovi la sua strada nello standard.




la std :: map è basata su un albero nero rosso . Puoi anche utilizzare altri containers per aiutarti a implementare i tuoi tipi di alberi.




Tutti i contenitori STL sono rappresentati esternamente come "sequenze" con un meccanismo di iterazione. Gli alberi non seguono questo idioma.







Related



Tags

c++ c++   stl   tree