Pourquoi le C++ STL ne pas fournir un “arbre” conteneurs?

Pourquoi le C++ STL ne pas fournir un "arbre" conteneurs, et quelle est la meilleure chose à utiliser à la place?

Je veux stocker une hiérarchie d'objets, comme un arbre, plutôt que d'utiliser un arbre comme une amélioration de la performance...

  • J'ai besoin d'un arbre à stocker une représentation d'une hiérarchie.
  • Je suis avec le mec qui a voté les "bonnes" réponses, qui semble être; "les Arbres sont inutiles". Il y a d'importantes si obscur utilise des arbres.
  • Je pense que la raison en est simple - pas de celui mis en œuvre dans la bibliothèque standard encore. C'est comme la norme de la bibliothèque n'avait pas std::unordered_map et std::unordered_set jusqu'à récemment. Et avant qu'il n'y a pas de conteneurs STL dans la bibliothèque standard du tout.
  • Mes pensées (n'ayant jamais lu la norme en question, cependant, c'est donc un commentaire n'est pas une réponse) sont que la STL ne se soucie pas de structures de données propres, il se soucie des spécifications en matière de complexité et que les opérations sont prises en charge. Donc, la structure sous-jacente utilisée peut varier entre les implémentations et/ou les architectures cibles, à condition de satisfaire aux spécifications. Je suis sûr que std::map et std::set va utiliser un arbre à chaque mise en œuvre, mais ils n'ont pas à si certains non-structure de l'arbre également conforme aux spécifications.
InformationsquelleAutor Roddy | 2008-10-15
  1. 177

    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

    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

    • Il y a beaucoup, beaucoup de raisons de l'utilisation d'un arbre, même si ceux-ci sont les plus courantes. La plupart des communes !l'égalité de tous.
    • Une troisième raison de vouloir un arbre est une liste triée avec la rapidité d'insertion/suppression, mais pour qu'il y est std:multiset.
    • Comment peut-on utiliser la carte pour l'arbre type de structure de données quand on ne connait pas la profondeur de l'arbre ??
    • Pas sûr de la manière dont la profondeur est pertinent quand vous êtes à l'aide de la carte triés contenant. Carte des garanties log(n) insertion/suppression/recherche (et contenant les éléments dans l'ordre de tri). Tout cela est de la carte est utilisé pour, est mis en œuvre (en général) comme un rouge/noir de l'arbre. Un rouge/noir de l'arbre permet de s'assurer que l'arbre est équilibré. Donc la profondeur de l'arbre est directement liée au nombre d'éléments dans l'arbre.
    • Je suis en désaccord avec cette réponse, à la fois en 2008 et aujourd'hui. La bibliothèque standard n'est pas "avoir des de" stimuler, et de la disponibilité de quelque chose de suralimentation ne devrait pas être (et n'a pas été une raison de ne pas l'adopter dans la norme. En outre, la BGL est générale et assez impliqué pour mérite spécialisé arborescence de classes indépendantes de lui. Aussi, le fait que std::map et std::set nécessitent un arbre, de l'OMI, un argument de plus pour avoir un stl::red_black_tree etc. Enfin, la std::map et std::set arbres sont équilibrés, un std::tree peut-être pas.
    • la disponibilité de quelque chose de suralimentation ne devrait pas être une raison de ne pas l'adopter dans la norme" - l'un des fins de boost est d'agir comme un terrain d'essai pour les bibliothèques utiles avant l'incorporation dans la norme, je ne peux que dire "absolument!".

    InformationsquelleAutor Martin York
  2. 92

    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.

    Certains problèmes à prendre en compte:

    - 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

    • "...pas de bonne façon de satisfaire tout le monde..." Sauf que depuis stl::map, stl::multimap, et stl::set sont basés sur les stl rb_tree, il devrait satisfaire tout comme de nombreux cas, comme ces types de base ne.
    • Vu qu'il n'y aucun moyen de récupérer les enfants d'un nœud d'un std::map, je ne qualifierais pas ces arbres conteneurs. Ceux sont des conteneurs associatifs qui sont couramment mis en œuvre par des arbres. Grande différence.
    • Je suis d'accord avec Meuglement de Canard, comment voulez-vous mettre en œuvre une largeur de recherche sur un std::map? Ça va être terriblement cher
    • J'ai commencé à utiliser Kasper Peeters' arbre.hh, cependant, après examen de la gestion des licences pour la GPLv3, ou de toute autre version de la GPL, il pourrait contaminer notre logiciel commercial. Je recommande de regarder treetree fournies dans le commentaire de @hplbsh si vous avez besoin d'une structure pour des fins commerciales.
    • En fait, Boost fournit un arbre contenant. La bibliothèque est appelée Boost.PropertyTree.
    • J'ai fini à l'aide de datasoftsolutions.net/tree_container_library/overview.php, j'ai essayé treetree mais la documentation est rare et d'utilisation très difficile. Coup de pouce.PropertyTree fonctionne bien avec des cordes, mais n'ai pas vu des exemples de l'utilisation de tout autre chose. TCL est d'en-tête uniquement, commercial convivial, et STL sympathique. Cela fonctionne bien pour mes besoins.
    • La variété des exigences spécifiques sur les arbres est un argument de différents types d'arbres, pas de rien du tout.
    • Serait-il possible de créer un modèle de classe ou structure qui peut agir comme un arbre, permettant à l'utilisateur de spécifier leurs besoins en tant que paramètres de modèle? J'imagine que ce serait la manière la plus générale pour mettre en œuvre une norme de l'arbre, bien qu'il serait susceptible d'être un peu maladroit.
    • Boost Graph Library fournit un R-tree.

    InformationsquelleAutor Greg Rogers
  3. 50

    De 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.

    • Je ne pense pas qu'il parle implémentations de conteneur, il parle d'un arbre actuelle conteneur lui-même.
    • Je pense que ce wilhelmtell signifie, c'est que le C++ de la bibliothèque standard ne définit pas de conteneurs, en se fondant sur leurs données sous-jacentes de la structure; il permet seulement de conteneurs par leur interface et de caractéristiques observables comme la performance asymptotique. Quand vous pensez à ce sujet, un arbre n'est pas vraiment un conteneur (comme nous les connaissons tous. Ils n'ont même pas d'un simple end() et begin() avec lequel vous pouvez parcourir tous les éléments, etc.
    • Non-sens sur tous les points. C'est une chose qui contient des objets. C'est très trivial de conception, il doit avoir un begin() et end() et itérateurs bidirectionnels pour itérer avec. Chaque conteneur possède des caractéristiques différentes. Il serait utile si l'on pourrait en outre avoir des caractéristiques de l'arbre. Devrait être assez facile.
    • Donc on veut avoir un conteneur qui fournit rapidement des recherches pour enfant et parent nœuds, et des besoins en mémoire.
    • De ce point de vue, aussi de cartes comme les files d'attente, des piles ou des files d'attente de priorité ne serait pas appartenir à la STL (ils n'ont pas begin() et end()). Et n'oubliez pas que la priorité de la file d'attente est habituellement d'un segment, dont au moins en théorie, est un arbre (même si implémentations réelles). Donc, même si vous avez mis en place un arbre comme un adaptateur à l'aide de différents sous-jacente de la structure de données, il serait admissible à être inclus dans la STL.
    • Certainement personne est à dire que seuls les conteneurs appartiennent à la STL. Conteneur cartes ne correspondent pas à la Container concept et ils sont évidemment dans la STL comme vous l'avez observé. Vous donnez priority_queue comme un exemple, mais je crois que vous conviendrez qu'il n'expose pas un arbre comme les comportements et utilise une structure arborescente pour un but très précis. Mais qu'en est générique arbres? Rappelez-vous que l'une des fonctions les plus importantes de une structure d'arbre est de modéliser les relations, qui ne sont pas toujours adhérer à l'arbre binaire de la structure.

    InformationsquelleAutor wilhelmtell
  4. 47

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

    C++11 est venu et reparti et ils n'avaient toujours pas voir la nécessité de proposer une 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 Les 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 définition une fourchette à l'intérieur d'une hiérarchie pourrait être un désordre d'affaires.

    • Si le projet peut permettre pour les enfants d'un tree_node pour être triés, puis à l'aide d'un std::set<> à la place de std::vector<> et puis l'ajout d'un opérateur<() à la tree_node objet qui améliorera grandement la recherche de la performance d'un " T " comme objet.
    • Il s'avère qu'ils étaient paresseux et effectivement faites votre premier exemple un Comportement Indéfini.
    • J'ai finalement décidé de demander le détail de votre commentaire here.
    • many of the algorithms simply don't make any sense for a hierarchy. Une question d'interprétation. Imaginez une structure de stackoverflow utilisateurs et chaque année, vous voulez ceux avec une plus grande quantité de points de réputation pour le patron ceux avec moins de points de réputation. Et donc de fournir des BFS itérateur et de comparaison appropriée, chaque année, vous venez d'exécuter std::sort(tree.begin(), tree.end()).
    • Par la même occasion, vous pourrait facilement construire un cadre associatif de l'arbre (pour le modèle non structuré de valeurs de clés de registres, comme JSON par exemple) par le remplacement de vector avec map dans l'exemple ci-dessus. Pour le support complet du format JSON comme la structure, vous pouvez utiliser variant pour définir les nœuds.
    InformationsquelleAutor nobar
  5. 43

    Si vous êtes à la recherche pour un RB-arbre de la mise en œuvre, puis stl_tree.h pourrait être approprié pour vous aussi.

    • Bizarrement c'est la seule réponse qui répond vraiment à la question d'origine.
    • Considérant qu'il veut un "Heiarchy", Il semble raisonnable de supposer que quoi que ce soit avec "l'équilibre" est la bonne réponse.
    • "C'est un fichier d'en-tête inclus par d'autres en-têtes de bibliothèque. Vous ne devriez pas tenter de l'utiliser directement."
    • La copie, il ne constitue pas l'utiliser directement.
    InformationsquelleAutor systemsfault
  6. 12

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

    • Il utilise habituellement des arbres rouge-noir (ce n'est pas nécessaire de le faire).
    • GCC utilise un arbre de mettre en œuvre la carte. Quelqu'un veux regarder leurs VC répertoire include de voir ce que microsoft utilise?
    • // Rouge-noir classe de l'arbre, conçu pour une utilisation dans la mise en œuvre de la STL // conteneurs associatifs (set, multiset, map et multimap). Saisi qu'à partir de mon stl_tree.h fichier.
    • Au moins dans le Studio 2010, il utilise un interne ordered red-black tree of {key, mapped} values, unique keys classe, définie dans <xtree>. N'ont pas accès à une version plus moderne à cet instant.
    InformationsquelleAutor J.J.
  7. 8

    Dans un sens, 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é. La probable raisonnement derrière ne comprenant pas un vrai arbre de structure de données est probablement juste une question de ne pas tout compris dans la stl. Le tsl peut être regardé comme un cadre pour l'utilisation dans la mise en œuvre de vos propres algorithmes et structures de données.

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

    Sinon, il y a un tas de les bibliothèques hors il y, selon les besoins de votre arbre.

    InformationsquelleAutor Eclipse
  8. 6

    Tous conteneur STL de l'extérieur sont représentés comme des "séquences" avec un mécanisme d'itération.
    Les arbres ne suivez pas cet idiome.

    • Une structure d'arbre de données pourrait fournir précommande, afinde ou postorder traversée par les itérateurs. En fait, c'est ce que std::map n'.
    • Oui et non ... ça dépend de ce que tu veux dire par "arbre". std::map est implémentée en interne comme l'arbre, mais de l'extérieur il apparaît comme une SÉQUENCE ordonnée de COUPLES. Étant donné quelle que soit l'élément, vous pouvez universellement demander qui est devant et qui est derrière. Un général de l'arbre de structures contenant des éléments dont chacun contient d'autres n'imposent pas de tri ou de la direction. Vous pouvez définir les itérateurs qui marche une arborescence de plusieurs façons (comme de la cire|deep premier|dernier ...) mais une fois que vous l'avez fait, un std::tree conteneur doit retourner l'un d'entre eux à partir d'un begin fonction. Et il n'y a pas de raison évidente pour retourner un ou l'autre.
    • Un std::map est généralement représenté par un équilibre binaire un arbre de recherche, pas un B-arbre. Le même argument que vous avez fait pourrait s'appliquer à std::unordered_set, il n'a pas d'ordre naturel, mais présente de début et de fin des itérateurs. L'exigence de début et de fin est juste qu'il parcourt tous les éléments dans certains déterministe de l'ordre, pas qu'il y a à être un fait naturel. précommande est parfaitement valide itération pour qu'un arbre.
    • "Une std::map est généralement représenté par un équilibre binaire un arbre de recherche, pas un B-arbre.": quel jeu jouez-vous? un arbre est une implémentation pour un arbre de recherche binaire et la carte n'est pas "représenté" en tant que tels. il est "mis en œuvre" en tant que tels. il est REPRÉSENTÉ comme une séquence ordonnée de couples qui commence à begin() et terminent juste avant la fin(). Il est vrai que vous pouvez marcher un arbre à partir de certains begin() jusqu'à une certaine fin(), mais, à moins que la définition d'un but pour elle (comme la carte n') il n'y a plus aucune idée que d'avoir des éléments dans une liste.
    • L'implication de votre réponse est qu'il n'y a pas de stl n-structure d'arbre de données, car il ne dispose pas d'une "séquence" de l'interface. C'est tout simplement incorrect.
    • Non: car il n'a pas une FAÇON UNIQUE de définir une séquence d'interface, car il est normal que le but est de ne pas être tout simplement de la séquence. Imposer comme "standard" de la défaite de l'avantage d'avoir une telle structure, et de ne pas imposer, il fera la structure inutile de respect pour <algorithm>, chaque conteneur est compatible avec. Vous pouvez toujours le faire vous-même, mais la façon dont vous allez le faire, en conflit avec la façon de quelqu'un d'autre, et il n'y a pas de raisons techniques à préférer l'une ou l'autre. Donc, il ne peut y avoir une façon "standard".
    • Comme en témoigne std::unordered_set, qui n'a pas de "façon unique" de l'itération de ses membres (en fait, l'itération d'ordre pseudo-aléatoire et la mise en œuvre définies), mais il est encore un conteneur stl - ce réfute votre point de vue. Itération sur chaque élément dans un conteneur est toujours utile, même si l'ordre n'est pas défini.
    • Je ne suis pas plus capable de userstand si c'est moi uncapable de l'expliquer ou de vous qui ne voulez pas comprendre. unordered_set a pas de façon unique de TRI, mais il a une façon unique de MARCHER: démarrer avec begin() et se termine avec end(), et peut être soumis à tout ce que <algorithm>. Mais un arbre avec une unique façon de MARCHER est inutile, car le but d'un arbre est d'être PROMENÉ dans au moins jusqu'-dowmn et gauche-droite. Si ma façon de parler n'est pas compréhensible pour vous, lisez ceci: stackoverflow.com/a/206011/924727 C'est exactement mon concept, avec d'autres mots.
    • Il n'y a aucune raison pour qu'un conteneur doit avoir une façon de marcher, il est possible de proposer différentes itération commandes par différents types de itérateur paires (voir, par exemple,rbegin/rend). Un std:arbre pourrait avoir quelque chose comme breadth_begin/breadth_end et depth_begin/depth_end pour le haut-bas et gauche-droite ordres respectivement. La réponse vous lien est correct, c'est le grand écart au potentiel de la structure qui conduit à lui à gauche en sortant de la bibliothèque standard, mais cela n'a rien à voir avec des "séquences" ou "une itération mécanisme".
    • Il a à faire, parce qu'ils sont la principale raison d'un tel écart. Se sentir libre de ne pas beleave, mais permettez-moi de croire en la paix avec dieu!
    • Je vois votre point de vue. Vous voulez être en mesure de choisir itération de la stratégie dans un arbre contenant a) parce que l'arbre de la sémantique correspond à vos données b) vous souhaitez parcourir l'arbre dans un spécifique pour résoudre un problème. Solution Possible: std::tree a un enumeral le modèle d'étiquette argument qui indique la valeur par défaut de la traversée à l'ordre donné par begin() pour gamme pour, dire. Ce modèle arg la valeur par défaut est-à-dire traversal::inorder. On pourrait même donner des noms aux autres: template<typename NodeT> using tree_pre<NoteT> = tree<NodeT, traversal::preorder>; etc. C'est une pratique de problème.
    • Dans d'autres nouvelles, beaucoup de travail est d'aller dans un itérateur bibliothèque pour le prochain standard. Peut-être quelque chose n'allait les aider.
    • Bonne suggestion. Bien sûr, 3 ans plus tard, quelque chose est en évolution, mais ... en fait, il a introduit un nouveau concept (plages), permettant en fait de briser un contraindre.

    InformationsquelleAutor Emilio Garavaglia
  9. 4

    Parce que le TSL n'est pas un "tout" de la bibliothèque. Il contient, en substance, le minimum de structures nécessaires pour construire des choses.

    • Arbres binaires sont extrêmement fonctionnalités de base, et en fait, plus de base que les autres conteneurs depuis les types comme std::map, std::multimap, et stl::set. Depuis ces types sont basés sur eux, vous vous attendez à ce que le type sous-jacent à être exposé.
    • Je ne pense pas que l'OP est en demande d'un binaire de l'arbre, il demande à un arbre pour stocker une hiérarchie.
    • Non seulement cela, l'ajout d'un arbre "conteneur" pour STL aurait moyen d'ajouter de nombreux de nombreux nouveaux concepts, par exemple un arbre navigator (généralisation Itérateur).
    • "Minimale des structures à construire des choses" est très subjective de la déclaration. Vous pouvez construire des choses avec les raw C++ concepts, donc je gues vrai minimum serait d'aucune STL à tous.
    InformationsquelleAutor Paul Nathan
  10. 4

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

    InformationsquelleAutor roffez
  11. 3

    De l'OMI, une omission. Mais je pense qu'il y a une bonne raison de ne pas inclure une Arborescence dans la STL. Il y a beaucoup de logique dans le maintien de l'arbre, qui est la mieux écrite que fonctions de membre dans la base TreeNode objet. Lorsque TreeNode est enveloppé dans une STL-tête, il est juste messier.

    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); } 
} ;
    • C'est beaucoup de posséder raw pointeurs que vous avez là, bon nombre n'ont pas besoin d'être des pointeurs à tous.
    • Vous suggérons de retirer cette réponse. Une classe TreeNode est la partie de l'arbre de la mise en œuvre.
    InformationsquelleAutor bobobobo
  12. 2

    Je pense qu'il y a plusieurs raisons pour lesquelles il n'existe pas de stl arbres. Principalement les Arbres sont une forme de structure de données récursive qui, à l'instar d'un conteneur (liste, vecteur, ensemble), est très différente de la structure fine qui rend le choix difficile. Ils sont également très faciles à construire dans la forme de base à l'aide de la STL.

    Finie enracinée arbre peut être considéré comme un conteneur qui a une valeur ou d'une charge, dire une instance de la classe et, éventuellement, un vide de collecte de enraciné (sous -) arbres; arbres qui vide de sous-arbres sont bien comme les 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
{};

    On a de penser un peu plus à propos de itérateur, design, etc. et qui produit et co-produit des opérations permet de définir et d'être efficace entre les arbres et l'original de la stl doit être bien écrit, alors que l'ensemble vide, d'un vecteur ou d'une liste contenant 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 le classique papiers de Boucherie, Grossman et Larsen; aussi les études de Connes et Kriemer pour des exemples de 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. Plutôt, ils facilitent les tâches qui, 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 au-dessus de tous, ont la propriété que si vous supprimez la racine, vous effacer tout.

    Considérer les itérateurs sur l'arbre, probablement, ils seraient réalisées comme une simple pile de itérateurs, à 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 où toutes les flèches de flux en direction de la racine de cette arborescence peut itéré si les itérateurs vers le trivial itérateur et de la racine; toutefois, il ne peut pas être navigué à travers ou vers le bas (les autres itérateurs ne sont pas connus pour ça) ni que l'ensemble des itérateurs être supprimé, sauf en gardant la trace de toutes les instances.

    Arbres sont très utiles, ils ont beaucoup de structure, ce qui en fait un sérieux défi pour obtenir le définitivement approche correcte. À mon avis, c'est pourquoi ils ne sont pas mis en œuvre dans la STL. 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 ont à faire face, c'est - ce qu'un type d'arbre représente - c'est un noeud contenant éventuellement vide de collecte de (petits) des arbres. Le langage courant le permet sans défi de fournir le constructeur par défaut pour container<B> ne pas allouer de l'espace sur le tas (ou ailleurs) pour un B, etc.

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

    InformationsquelleAutor tjl
  13. -8

    Tous les conteneurs STL peut être utilisé avec des itérateurs. Vous ne pouvez pas avoir un itérateur d'un arbre, parce que vous n'avez pas de "bonne" façon de faire passer par l'arbre.

    • Mais vous pouvez dire BFS ou DFS est la bonne manière. Ou de soutien les deux. Ou tout autre que vous pouvez imaginer. Jut indiquer à l'utilisateur ce qu'il est.
    • dans std::map il y a l'arbre itérateur.
    • Un arbre peut définir ses propres itérateur de type qui parcourt tous les nœuds dans l'ordre d'une "extrême" de l'autre (c'est à dire pour tout arbre binaire avec les chemins de 0 & 1, elle pourrait offrir un itérateur qui va de "0" à "tous les 1", et un itérateur inverse, qui fait le contraire; pour un arbre avec une profondeur de 3 et le nœud de départ s, par exemple, il peut effectuer une itération sur les nœuds s000, s00, s001, s0, s010, s01, s011, s, s100, s10, s101, s1, s110, s11, s111 ("de gauche" à la "droite"); il peut également utiliser une profondeur de traversée de modèle (s, s0, s1, s00, s01, s10, s11,
    • etc.), ou un autre motif, aussi longtemps que il itère sur chaque nœud de telle manière que chacun d'eux n'est passé qu'une seule fois.
    • Je ne comprends pas pourquoi cette réponse ont été si mal downvoted. C'est la seule qui répond vraiment à la question. L'arbre ne fait pas partie de l'interface STL (bien que c'est là l'interne) parce qu'un Arbre n'est pas un Conteneur de la STL sens, qui est, il n'est pas un conteneur d'éléments linéaires itération. (Par exemple, il n'aura pas un unique begin() et end()). L'ajout d'un arbre pour STL aurait moyen d'ajouter de nombreux de nombreux nouveaux concepts, par exemple un arbre navigator (généralisation Itérateur).
    • quel est le problème avec la définition de begin() comme un nœud racine et end() comme une dernière feuille?
    • il y a beaucoup de feuilles de cours, et même si vous choisissez l'un comme le dernier il n'y a pas qu'une seule façon de marcher les trois de façon linéaire.
    • vous pouvez choisir n'importe quel de la DFS ou BFS comme tomas789 souligné déjà. J'ai mis en œuvre les itérateurs pour mon arbre-comme des structures à plusieurs reprises.
    • bien sûr, mais la transversale n'est pas unique comme dans une séquence. Un graphique général peut être DFS ou BFS transversed et ce n'est pas pour en faire une séquence. Elles peuvent être considérées comme de la séquence, mais c'est différent.
    • std bibliothèque n'est pas limitted de séquences, std::unordered_map n'est pas un ordre, mais il existe déjà dans la bibliothèque standard. Il n'y a pas une telle chose comme "unique " itération" ou "unique " traversée". Même avec un tableau vous pourriez parcourir dans n'importe quelle manière que vous aimez. Les itérateurs résoudre ce problème exactement et de fournir une couche d'abstraction, de sorte que vous pouvez effectuer une itération sur des structures comme std::map. C'est tout une question de convention.
    • très bon point. Je pense que std::unordered_set a été "fabriqué" une séquence parce que nous ne savons pas de meilleure façon de l'itération sur les éléments autres que certains arbitraire (interne donnée par la fonction de hachage). Je pense que c'est le cas inverse de l'arbre: l'itération sur unordered_set est underspecified, en théorie, il n'y a "aucun moyen" de la définition d'une itération d'autres que peut-être "au hasard". Dans le cas de l'arbre il y a beaucoup de "bonnes" (non aléatoire) des moyens. Mais, encore une fois, votre point est valide.

    InformationsquelleAutor 7890