Pourquoi le C++ STL ne fournit-il aucun conteneur" arborescent"?

probablement pour la même raison qu'il n'y a pas de container d'arbre dans 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 satisfaire tous ceux qui l'utiliseraient.

Quelques questions à prendre en considération:

- 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 fournir? - différents itérateurs, algorithmes de recherche, etc.

en fin de compte, le problème finit par être qu'un container d'arbre qui serait assez utile à tout le monde, serait trop lourd pour satisfaire la plupart des gens qui l'utilisent. Si vous cherchez quelque chose de puissant, Boost Graph Library est essentiellement un super-ensemble de ce qu'une bibliothèque d'arbre pourrait être utilisé pour.

Voici d'autres implémentations génériques de tree:

- Arbre de Kasper Peeters.hh

- Forêt D'Adobe

- core:: tree

la philosophie du STL est que vous choisissez un conteneur basé sur des garanties et non sur la façon dont le conteneur est mis en œuvre. Par exemple, votre choix de conteneur peut être basé sur un besoin de recherche rapide. Pour tout ce qui vous concerne, le conteneur peut être implémenté comme une liste unidirectionnelle -- aussi longtemps que la recherche est très rapide, vous seriez heureux. C'est parce que vous ne touchez pas les internes de toute façon, vous utilisez des itérateurs ou des fonctions de membre pour l'accès. Votre code n'est pas lié à la façon dont container est mis en œuvre mais à quelle vitesse il est, ou si elle a un ordre fixe et défini, ou si elle est efficace sur l'espace, et ainsi de suite.

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

C++11 est venu et est parti et ils n'ont toujours pas vu la nécessité de fournir un std::tree , bien que l'idée ait été soulevée (voir ici ). Peut-être la raison pour laquelle ils n'ont pas ajouté ceci est qu'il est trivialement facile de construire votre propre sur le dessus des conteneurs existants. Exemple...

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

une traversée simple utiliserait la récursion...

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 algorithmes STL , alors les choses peuvent se compliquer. Vous pouvez construire vos propres itérateurs et obtenir une certaine compatibilité, mais beaucoup d'algorithmes n'ont tout simplement pas de sens pour une hiérarchie (tout ce qui change l'ordre d'une plage, par exemple). Même définissant une gamme dans une hiérarchie pourrait être un affaires confuses.

si vous recherchez une implémentation RB-tree, puis stl_tree.h pourrait être approprié pour vous aussi.

la std::map est basé sur un "151910920 rouge" l'arbre noir . Vous pouvez également utiliser d'autres conteneurs pour vous aider à mettre en œuvre vos propres types d'arbres.

, std::map est un arbre (il est nécessaire d'avoir les mêmes caractéristiques qu'un équilibre de l'arbre binaire), mais il n'expose pas d'autres arbres de la fonctionnalité. Le raisonnement probable derrière ne pas inclure une structure de données d'arbre réelle était probablement juste une question de ne pas inclure tout dans le LTS. Le LTS peut être considéré comme un cadre à utiliser dans la mise en œuvre de vos propres algorithmes et structures de données.

en général, s'il y a une fonctionnalité de bibliothèque de base que vous voulez, ce n'est pas dans le stl, la solution est de regarder BOOST .

sinon , il y a un bunch de bibliothèques out there , selon les besoins de votre arbre.

tous les conteneurs STL sont représentés extérieurement sous la forme de "séquences" avec un mécanisme d'itération. Les arbres ne suivent pas cet idiome.

parce que le STL n'est pas une bibliothèque "tout". Il contient, essentiellement, les structures minimales nécessaires pour construire les choses.

celui-ci semble prometteur et semble être ce que vous cherchez: http://tree.phi-sci.com/

de l'OMI, une omission. Mais je pense qu'il y a de bonnes raisons de ne pas inclure une structure arborescente dans le LTS. Il y a beaucoup de logique dans le maintien d'un arbre, qui est le mieux écrit comme fonctions de membre dans la base TreeNode objet . Quand TreeNode est enveloppé dans un en-tête STL, il devient plus désordonné.

par exemple:

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

je pense qu'il y a plusieurs raisons pour lesquelles il n'y a pas d'arbres stl. Les arbres sont principalement une forme de structure de données récursive qui, comme un conteneur (list, vector, set), a une structure fine très différente qui rend les bons choix difficiles. Ils sont également très faciles à construire dans la forme de base en utilisant le STL.

un arbre à racines finies peut être considéré comme un conteneur qui a une valeur ou une charge utile, disons une instance d'une classe A et, une collection éventuellement vide de racines (sub) arbres; les arbres qui sont vides de sous-arbres sont considérés comme des feuilles.

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

il faut penser un peu à la conception de l'itérateur, etc. et quelles opérations produit et co-produit on permet de définir et d'être efficace entre les arbres - et le LTS original doit être bien écrit - de sorte que l'ensemble vide, vecteur ou conteneur de liste est vraiment vide de toute charge utile dans le cas par défaut.

les Arbres jouent un rôle essentiel dans de nombreuses structures mathématiques (voir les documents classiques de Butcher, Grossman et Larsen; aussi les documents de Connes et Kriemer pour des exemples d'ils peuvent être joints, et comment ils sont utilisés pour énumérer). Il n'est pas correct de penser que leur rôle est simplement de faciliter certaines autres opérations. Ils facilitent plutôt ces tâches en raison de leur rôle fondamental en tant que structure de données.

Cependant, en plus des arbres il y a aussi des "co-arbres"; les arbres ont surtout la propriété que si vous supprimez la racine vous supprimez tout.

considère itérateurs sur l'arbre, probablement ils seraient réalisés comme une simple pile d'itérateurs, à un noeud, et à son parent,... jusqu'à la racine.

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

cependant, vous pouvez en avoir autant que vous voulez; collectivement ils forment un "arbre" mais où toutes les flèches coulent dans la direction vers la racine, ce Co-arbre peut itéré par des itérateurs vers l'itérateur trivial et la racine; cependant, il ne peut pas être navigué à travers ou vers le bas (les autres itérateurs ne sont pas connus), ni l'ensemble des itérateurs être supprimé, sauf en gardant la trace de toutes les instances.

arbres sont incroyablement utiles, ils ont beaucoup de structure, ce qui rend un défi sérieux pour obtenir l'approche définitivement correcte. À mon avis, c'est la raison pour laquelle ils ne sont pas mis en œuvre dans le TSL. En outre, dans le passé, j'ai vu des gens religieux et de trouver l'idée d'un type de récipient contenant des instances de son propre type difficile - mais ils doivent y faire face - c'est ce que représente un type d'arbre - c'est un noeud contenant une collection probablement vide d'arbres (plus petits). Le langage courant le permet sans contestation, à condition que le constructeur par défaut pour container<B> n'alloue pas d'espace sur le tas (ou ailleurs) pour un B , etc.

je serais heureux, si ce n', dans une bonne forme, trouver son chemin dans la norme.

tous les conteneurs STL peuvent être utilisés avec des itérateurs. Vous ne pouvez pas avoir un itérateur un arbre, parce que vous n'avez pas "un droit" chemin passer à travers l'arbre.