L'absence de conteneurs d'arborescence dans la STL C

La bibliothèque de modèles standard C (STL) n'offre aucun conteneur "d'arborescence" . Cette omission pose la question : pourquoi ? Et quelles sont les alternatives appropriées ?

Pourquoi aucun conteneur d'arborescence dans STL ?

Il y a deux raisons pour lesquelles on pourrait désirer une structure de données arborescente :

1. Représentation hiérarchique des objets : Modélisation d'une hiérarchie d'objets arborescente dans le code à l'aide d'une structure arborescente.

2. Caractéristiques d'accès efficaces : Assurer un accès rapide aux éléments en fonction de relations d'ordre, similaires aux arbres de recherche binaires.

Alternatives pour les structures arborescentes

• Boost Graph Library : Pour représenter des graphiques arbitraires, y compris des structures hiérarchiques.

• Ordonné Conteneurs associatifs :

  • std::map et std::multimap : mappe les clés aux valeurs, classées par clé.
  • std::set et std::multiset : Collections d'éléments uniques, classés par valeur.

Ces conteneurs fonctionnent efficacement comme des arbres binaires équilibrés, garantissant des temps d'accès logarithmiques efficaces. pour les insertions, les suppressions et les recherches. Ils offrent également des avantages supplémentaires, tels que :

• Parcours itérateur en temps constant des éléments dans un ordre trié.
• Logique de comparaison intégrée pour l'ordre des clés.
• Interfaces génériques, leur permettant de fonctionner avec n'importe quel type de clé prenant en charge la comparaison opérateurs.

Exemple :

Si l'on souhaite stocker une hiérarchie d'employés, avec un PDG à la racine et plusieurs niveaux de subordonnés, on peut utiliser un std::map<:string std::vector>>. Ici, les clés de carte seraient les noms des employés et les vecteurs associés contiendraient les noms de leurs subordonnés directs.

Conclusion

Bien que le C STL ne fournisse pas directement des conteneurs arborescents, il offre des alternatives appropriées à la fois pour la représentation hiérarchique et les caractéristiques d'accès efficaces. La bibliothèque de graphiques de Boost peut gérer des structures graphiques complexes, tandis que les conteneurs associatifs ordonnés fournissent un accès arborescent avec une interface générique et bien établie.