Pourquoi le C ++ STL ne fournit-il pas de conteneurs «arborescents»?

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

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

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

Vous voulez refléter le problème en utilisant une structure arborescente:
pour cela, nous avons une bibliothèque de graphiques boost

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

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

Fondamentalement, les caractéristiques de ces deux conteneurs sont telles qu'ils doivent pratiquement être mis en œuvre à l'aide d'arbres (bien que ce ne soit pas réellement une exigence).

Voir aussi cette question: Implémentation de l'arborescence C

Probablement pour la même raison qu'il n'y a pas de conteneur d'arbre en boost. Il existe de nombreuses façons de mettre en œuvre un tel conteneur, et il n'y a pas de bon moyen de satisfaire tous ceux qui l'utiliseraient.

Quelques points à considérer:

• Le nombre d'enfants pour un nœud est-il fixe ou variable?
• Combien de frais généraux par nœud? - c'est-à-dire, avez-vous besoin de pointeurs parents, de pointeurs frères, etc.
• Quels algorithmes proposer? - différents itérateurs, algorithmes de recherche, etc.

En fin de compte, le problème finit par être qu'un conteneur d'arbre qui serait suffisamment utile à tout le monde serait trop lourd pour satisfaire la plupart des personnes qui l'utilisent. Si vous recherchez quelque chose de puissant, Boost Graph Library est essentiellement un surensemble de ce à quoi une bibliothèque d'arborescence pourrait être utilisée.

Voici quelques autres implémentations d'arbres génériques:

• Arbre de Kasper Peeters.hh
• Forêt d'Adobe
• core :: tree

La philosophie de la STL est que vous choisissez un conteneur en fonction de garanties et non en fonction de la façon dont le conteneur est mis en œuvre. Par exemple, votre choix de conteneur peut être basé sur un besoin de recherches rapides. Pour tous vos soucis, le conteneur peut être implémenté comme une liste unidirectionnelle - tant que la recherche est très rapide, vous seriez heureux. C'est parce que vous ne touchez pas aux internes de toute façon, vous utilisez des itérateurs ou des fonctions membres pour l'accès. Votre code n'est pas lié à la façon dont le conteneur est implémenté, mais à sa vitesse, à son ordre fixe et défini, à son efficacité sur l'espace, etc.

"Je veux stocker une hiérarchie d'objets sous forme d'arbre"

C ++ 11 est venu et est parti et ils ne voyaient toujours pas la nécessité de fournir un std::tree, bien que l'idée soit venue (voir ici ). Peut-être que la raison pour laquelle ils n'ont pas ajouté cela est qu'il est trivialement facile de construire le vôtre au-dessus des conteneurs existants. Par exemple...

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

Une traversée simple utiliserait 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 que vous voulez qu'elle fonctionne avec les algorithmes STL , alors les choses peuvent se compliquer. Vous pouvez créer vos propres itérateurs et obtenir une certaine compatibilité, mais de nombreux algorithmes n'ont tout simplement aucun sens pour une hiérarchie (tout ce qui change l'ordre d'une plage, par exemple). Même la définition d' une plage au sein d'une hiérarchie pourrait être une entreprise compliquée.

Si vous recherchez une implémentation de l'arborescence RB, stl_tree.h peut également vous convenir.

la carte std :: est basée sur un arbre rouge noir . Vous pouvez également utiliser d'autres conteneurs pour vous aider à implémenter vos propres types d'arbres.

D'une certaine manière, std :: map est un arbre (il doit avoir les mêmes caractéristiques de performance qu'un arbre binaire équilibré) mais il n'expose pas d'autres fonctionnalités d'arbre. Le raisonnement probable derrière l'inclusion d'une véritable structure de données d'arbre était probablement juste une question de ne pas tout inclure dans la stl. La stl peut être considérée comme un cadre à utiliser pour implémenter 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 souhaitez, qui n'est pas dans la stl, le correctif est de regarder BOOST .

Sinon, il y a un tas de bibliothèques sur il , en fonction des besoins de votre arbre.

Tous les conteneurs STL sont représentés en externe comme des "séquences" avec un mécanisme d'itération. Les arbres ne suivent pas cet idiome.

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

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

OMI, une omission. Mais je pense qu'il y a une bonne raison de ne pas inclure une structure arborescente dans la STL. Il y a beaucoup de logique dans la maintenance d'une arborescence, qui est mieux écrite en tant que fonctions membres dans l' TreeNodeobjet de base . Quand TreeNodeest enveloppé dans un en-tête STL, il devient plus compliqué.

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 (liste, vecteur, ensemble), a une structure fine très différente qui rend les choix corrects délicats. Ils sont également très faciles à construire sous forme de base à l'aide de la STL.

Un arbre enraciné fini peut être considéré comme un conteneur qui a une valeur ou une charge utile, par exemple une instance d'une classe A et, une collection éventuellement vide d'arbres (sous) enracinés; les arbres avec une collection vide 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 aux opérations de produit et de coproduit qui permettent de définir et d'être efficace entre les arbres - et la STL d'origine doit être bien écrite - de sorte que l'ensemble vide, le vecteur ou le conteneur de liste soit 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 articles classiques de Butcher, Grossman et Larsen; aussi les articles de Connes et Kriemer pour des exemples de leur assemblage, 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 existe également des «co-arbres»; les arbres ont surtout la propriété que si vous supprimez la racine, vous supprimez tout.

Considérez les itérateurs sur l'arborescence, ils seraient probablement réalisés comme une simple pile d'itérateurs, vers un nœud 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 le souhaitez; collectivement, ils forment un "arbre" mais là où toutes les flèches circulent dans la direction de la racine, ce co-arbre peut être itéré à travers des itérateurs vers l'itérateur et la racine triviaux; cependant, il ne peut pas être parcouru à travers ou vers le bas (les autres itérateurs ne le connaissent pas), ni l'ensemble des itérateurs ne peut être supprimé sauf en gardant une trace de toutes les instances.

Les arbres sont incroyablement utiles, ils ont beaucoup de structure, ce qui en fait un défi sérieux pour obtenir l'approche définitivement correcte. À mon avis, c'est pourquoi ils ne sont pas mis en œuvre dans la STL. De plus, dans le passé, j'ai vu des gens devenir religieux et trouver l'idée d'un type de conteneur 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 nœud contenant un collection éventuellement vide d'arbres (plus petits). Le langage actuel le permet sans problème en fournissant le constructeur par défaut pour container<B>n'alloue pas d'espace sur le tas (ou n'importe où ailleurs) pour un B, etc.

Pour ma part, je serais ravi que cela, dans une bonne forme, trouve sa place dans la norme.

En lisant les réponses ici, les raisons citées sont que l'on ne peut pas parcourir l'arbre ou que l'arbre n'assume pas l'interface similaire aux autres conteneurs STL et qu'on ne peut pas utiliser d'algorithmes STL avec une telle structure d'arbre.

Ayant cela à l'esprit, j'ai essayé de concevoir ma propre structure de données arborescente qui fournira une interface de type STL et sera utilisable avec les algorithmes STL existants autant que possible.

Mon idée était que l'arborescence doit être basée sur les conteneurs STL existants et qu'elle ne doit pas masquer le conteneur, afin qu'il soit accessible à utiliser avec les algorithmes STL.

L'autre caractéristique importante que l'arborescence doit fournir est les itérateurs de déplacement.

Voici ce que j'ai pu trouver: https://github.com/igagis/utki/blob/master/src/utki/tree.hpp

Et voici les tests: https://github.com/igagis/utki/blob/master/tests/tree/tests.cpp

Tous les conteneurs STL peuvent être utilisés avec des itérateurs. Vous ne pouvez pas avoir un itérateur ou un arbre, parce que vous n'avez pas le droit de passer par l'arbre.