Pourquoi le LIST C ++ ne fournit-il pas de conteneurs "arborescents"?

Question

Pourquoi le STL C ++ ne fournit-il pas de conteneurs "arborescents", et quelle est la meilleure chose à utiliser à la place?

Je veux stocker une hiérarchie d'objets en tant qu'arbre, plutôt que d'utiliser un arbre comme amélioration des performances ...

Answer 1

Il y a deux raisons pour lesquelles vous pourriez vouloir utiliser un arbre:

Vous souhaitez mettre en miroir le problème en utilisant une structure arborescente:
Pour cela, nous avons boost graph library

Ou vous voulez un conteneur qui a arbre comme l'accès des caractéristiques Pour cela, nous avons

• std::map
• std::set

Fondamentalement, les caractéristiques de ces deux conteneurs est telle qu'ils ont à peu près la mise en œuvre d'arbres (si ce n'est en fait pas une obligation).

Voir aussi cette question: C arbre de la mise en Œuvre

Answer 2

Probablement pour la même raison qu'il n'existe pas d'arbre conteneur en boost. Il existe de nombreuses façons de mettre en œuvre un tel conteneur, et il n'y a pas de bonne façon de répondre à toutes les personnes qui voudraient l'utiliser.

Quelques points à considérer:
- Le nombre d'enfants d'un nœud fixe ou variable?
- Combien de frais généraux par nœud? - c'est à dire, avez-vous besoin d'parent pointeurs, frère ou sœur, pointeurs, etc.
- Quels algorithmes? - les différents itérateurs, les algorithmes de recherche, etc.

En fin de compte, le problème finit par n'être qu'un arbre contenant qui serait utile assez pour tout le monde, serait trop lourd pour satisfaire la plupart des gens à l'utiliser. Si vous êtes à la recherche de quelque chose de puissant, Boost Graph Library est essentiellement un sur-ensemble de ce qu'est un arbre de la bibliothèque pourrait être utilisé pour.

Voici quelques autres génériques arbre implémentations:
- Kasper Peeters' arbre.hh
- Adobe forêt
- core::arbre

Answer 3

"Je veux stocker une hiérarchie d'objets comme un arbre"

C++11 est venu et reparti et ils n'avaient toujours pas voir un besoin de fournir de l' std::tree, bien que l'idée ne viennent (voir ici). Peut-être la raison pour laquelle ils n'ont pas ajouté c'est que c'est trivial à construire votre propre sur le dessus de l'existant conteneurs. Par exemple...

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

Un simple traversal serait d'utiliser la récursivité...

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

Si vous voulez maintenir une hiérarchie et vous voulez qu'il fonctionne avec des algorithmes de la STL, alors les choses peuvent se compliquer. Vous pouvez construire votre propre itérateurs et d'atteindre une certaine compatibilité, cependant, la plupart des algorithmes n'ont tout simplement pas de sens pour une hiérarchie (tout ce qui modifie l'ordre d'une plage, par exemple). Même la définition d' une fourchette à l'intérieur d'une hiérarchie pourrait être un désordre d'affaires.

Answer 4

La STL philosophie est que vous choisissez un conteneur en fonction des garanties et ne repose pas sur la façon dont le conteneur est mis en œuvre. Par exemple, le choix de votre conteneur peut être fondée sur un besoin de rapidité des recherches. Pour tous les soins, le conteneur peut être mis en œuvre comme une unidirectionnel liste -- aussi longtemps que la recherche est très rapide, vous seriez heureux. C'est parce que vous n'êtes pas toucher les composants internes de toute façon, vous êtes en utilisant les itérateurs ou des fonctions de membre pour l'accès. Votre code n'est pas lié à la façon dont le conteneur est mis en œuvre, mais à la façon dont il est rapide, ou si elle est fixe et défini de la commande, ou si elle est efficace sur l'espace, et ainsi de suite.

Answer 5

Si vous cherchez une implémentation RB-tree, alors stl_tree.h pourrait vous convenir.