Por que o C ++ STL não fornece quaisquer recipientes de “árvore”?

Question

Por que o C ++ STL não fornece quaisquer recipientes de "árvore", e qual é a melhor coisa para usar em vez disso?

Eu quero armazenar uma hierarquia de objetos como uma árvore, em vez de usar uma árvore como um desempenho aprimoramento ...

Answer 1

Há duas razões que você poderia querer usar uma árvore:

Você deseja espelhar o problema usando uma estrutura de árvore:
Para isso temos impulso biblioteca gráfico

Ou você quer um recipiente que tem árvore como características de acesso Para isso temos

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

Basicamente as características desses dois recipientes é tal que eles praticamente têm de ser implementadas usando árvores (embora este não é realmente um requisito).

Veja também esta pergunta: Implementação árvore C

Answer 2

Provavelmente pela mesma razão que não há nenhum recipiente árvore no impulso. Há muitas maneiras de implementar um tal recipiente, e não há nenhuma boa maneira de satisfazer a todos que iria utilizá-lo.

Algumas questões a considerar:
- É o número de crianças para um nó fixo ou variável
? - Quanto sobrecarga por nó? - ou seja, você precisa de ponteiros pai, ponteiros irmãos, etc.
- Quais algoritmos para fornecer? -. Diferentes iteradores, algoritmos de busca, etc

No final, as extremidades problema sendo que um recipiente de árvore que seria suficiente útil para todos, seria muito pesado para satisfazer a maioria das pessoas a usá-lo. Se você está procurando algo poderoso, impulso Graph Library é essencialmente um subconjunto do que uma biblioteca árvore poderia ser utilizado.

Aqui estão algumas outras implementações de árvores genéricas:
- Kasper Peeters' tree.hh
- floresta do Adobe
- núcleo :: árvore

Answer 3

A filosofia da STL é que você escolher um recipiente com base em garantias e não com base em como o recipiente é implementado. Por exemplo, a escolha do recipiente pode ser baseada em uma necessidade para pesquisas rápidas. Por tudo o que importa, o recipiente pode ser implementada como uma lista unidirecional - desde que a pesquisa é muito rápido você ficaria feliz. Isso é porque você não está tocando a parte interna de qualquer maneira, você está usando iteradores ou funções de membro para o acesso. Seu código não está vinculada à forma como o recipiente é implementado, mas para o quão rápido ele é, ou se tem uma ordem fixa e definida, ou se é eficiente no espaço, e assim por diante.

Answer 4

"Eu quero armazenar uma hierarquia de objetos como uma árvore"

C ++ 11 tem ido e vindo e eles ainda não viu uma necessidade de proporcionar um std::tree, embora a idéia veio para cima (veja aqui ). Talvez a razão pela qual eles não têm adicionado este é que é tão fácil de construir o seu próprio no topo dos recipientes existentes. Por exemplo ...

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

A simples travessia usaria recursão ...

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

Se você quiser manter uma hierarquia e que você quer que ele funcione com STL algoritmos , então as coisas podem ficar complicadas. Você poderia construir seus próprios iteradores e obter alguma compatibilidade, porém muitos dos algoritmos simplesmente não faz qualquer sentido de uma hierarquia (qualquer coisa que altera a ordem de um intervalo de, por exemplo). Mesmo definição uma gama dentro de uma hierarquia pode ser um negócio sujo.

Answer 5

Se você está procurando uma implementação RB-árvore, em seguida, stl_tree.h pode ser apropriado para você também.

Answer 6

o std :: mapa é baseado em um vermelho árvore preta. Você também pode usar outro recipientes para ajudar a implementar seus próprios tipos de árvores.

Answer 7

De certa forma, std :: mapa é uma árvore (ele é obrigado a ter as mesmas características de desempenho como uma árvore binária equilibrada), mas não expõe outras funcionalidades árvore. O raciocínio por trás provavelmente não incluindo uma estrutura de dados árvore real foi provavelmente apenas uma questão de não incluir tudo no stl. O STL pode ser encarado como uma estrutura para uso na implementação de seus próprios algoritmos e estruturas de dados.

Em geral, se há uma funcionalidade de biblioteca básica que você quer, que não está no STL, a correção é olhar para REFORÇO .

Caso contrário, há um bando de bibliotecas out há , dependendo das necessidades de sua árvore.

Answer 8

Todos recipiente STL são externamente representado como "sequências" com um mecanismo de iteração. Árvores não seguem esse idioma.

Answer 9

Uma vez que o STL não é uma biblioteca "tudo". Ele contém, essencialmente, as estruturas mínimas necessárias para as coisas de construção.

Answer 10

Este parece promissor e parece ser o que você está procurando: http://tree.phi-sci.com/

Answer 11

IMO, uma omissão. Mas eu acho que há uma boa razão para não incluir uma estrutura de árvore na STL. Há um monte de lógica na manutenção de uma árvore, que é melhor escrito como funções de membro para o objeto base TreeNode . Quando TreeNode é embrulhado em um cabeçalho STL, ele só fica mais confusa.

Por exemplo:

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

Answer 12

Eu acho que há várias razões pelas quais não há árvores STL. Principalmente árvores são uma forma de estrutura de dados recursiva que, como um recipiente (lista, vetor, conjunto), tem estrutura fina muito diferente que faz as escolhas corretas complicado. Eles também são muito fáceis de construir, em forma básica usando o STL.

Uma árvore finita enraizada pode ser pensado como um recipiente que tem um valor ou payload, dizer uma instância de uma classe A e, uma coleção possivelmente vazio de (sub) árvores enraizadas; árvores que esvaziam de sub-árvores são embora, como as folhas.

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

Um tem que pensar um pouco sobre iterador projetar etc. e que as operações de produtos e co-produtos One permite definir e ser eficiente entre as árvores - ea STL original tem de ser bem escrito - de modo que o conjunto vazio, vetor ou recipiente lista é realmente vazia de qualquer carga útil no caso padrão.

As árvores desempenham um papel essencial em muitas estruturas matemáticas (veja os papéis clássicos de Butcher, Grossman e Larsen; também os papéis de Connes e Kriemer para exemplos de que eles podem ser unidos, e como eles são usados ??para enumerar). Não é correto pensar seu papel é simplesmente para facilitar certas outras operações. Ao contrário, eles facilitam as tarefas por causa de seu papel fundamental como uma estrutura de dados.

No entanto, além de árvores também são "co-árvores"; as árvores acima de tudo ter a propriedade que se eliminar a raiz de excluir tudo.

Considere iterators na árvore, provavelmente eles iriam ser realizado como uma simples pilha de iteradores, a um nó, e seu pai, ... até a raiz.

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

No entanto, você pode ter como muitos como você gosta; colectivamente, eles formam uma "árvore", mas onde todas as setas de fluxo na direcção para a raiz, esta co-árvore pode iterado embora iterators no sentido da iteração trivial e raiz; no entanto, não pode ser navegado através de ou para baixo (os outros iteradores não são conhecidos por ele) nem pode o conjunto de iteradores ser excluído, exceto por manter o controle de todas as instâncias.

As árvores são extremamente útil, eles têm um monte de estrutura, o que torna um desafio sério para obter a abordagem definitivamente correta. A meu ver é por isso que eles não são implementados no STL. pessoas Além disso, no passado, eu vi obter religiosa e encontrar a idéia de um tipo de recipiente que contém instâncias de seu próprio tipo de desafio - mas eles têm de enfrentá-lo - que é o que um tipo de árvore representa - é um nó que contém uma possivelmente recolha vazio de árvores (mais pequenas). O idioma atual permite isso sem desafio fornecendo o construtor padrão para container<B> não aloca espaço na pilha (ou em qualquer outro lugar) para um B, etc.

Eu, pelo menos ficaria satisfeito se este fez, de uma forma boa, encontrar seu caminho para o padrão.

Answer 13

Todos os contêineres STL pode ser usado com iteradores. Você não pode ter um iterador uma uma árvore, porque você não tem '' caminho certo '' maneira atravessam a árvore.