¿Por qué C ++ STL no proporciona ningún contenedor “árbol”?

¿Por qué el C ++ STL no proporciona ningún contenedor “árbol“, y qué es lo mejor para usar en su lugar?

Quiero almacenar una jerarquía de objetos como un árbol, en lugar de usar un árbol como una mejora de rendimiento …

Hay dos razones por las que podría querer usar un árbol:

Desea reflejar el problema utilizando una estructura similar a un árbol:
Para esto tenemos una biblioteca de gráficos de impulso

O quieres un contenedor que tenga características de acceso tipo árbol. Para esto tenemos

  • std::map
  • std::set

Básicamente, las características de estos dos contenedores son tales que prácticamente deben implementarse utilizando árboles (aunque esto no es realmente un requisito).

Ver también esta pregunta: Implementación del árbol C

Probablemente por la misma razón que no hay un contenedor de árbol en potencia. Hay muchas formas de implementar dicho contenedor, y no hay una buena manera de satisfacer a todos los que lo usarían.

Algunos asuntos a considerar:
– ¿El número de hijos de un nodo es fijo o variable?
– ¿Cuánto sobrecarga por nodo? – es decir, ¿necesita punteros de los padres, punteros de hermanos, etc.
– ¿Qué algoritmos ofrecer? – iteradores diferentes, algoritmos de búsqueda, etc.

Al final, el problema termina siendo que un contenedor de árbol que sería lo suficientemente útil para todos, sería demasiado pesado para satisfacer a la mayoría de las personas que lo usan. Si está buscando algo poderoso, Boost Graph Library es esencialmente un superconjunto de lo que una biblioteca de árbol podría ser utilizada.

Aquí hay algunas otras implementaciones genéricas de árbol:
– Kasper Peeters ‘tree.hh
– Bosque de Adobe
– core :: tree

La filosofía de STL es que elija un contenedor basado en garantías y no en función de cómo se implemente el contenedor. Por ejemplo, su elección de contenedor puede basarse en la necesidad de búsquedas rápidas. Por lo que a usted le importa, el contenedor puede implementarse como una lista unidireccional, siempre y cuando la búsqueda sea muy rápida, sería feliz. Eso es porque no estás tocando las partes internas de ninguna manera, estás usando iteradores o funciones miembro para el acceso. Su código no está vinculado a la forma en que se implementa el contenedor, sino a la rapidez con que lo hace, o si tiene un orden fijo y definido, o si es eficiente en el espacio, y así sucesivamente.

“Quiero almacenar una jerarquía de objetos como un árbol”

C ++ 11 ha venido y se ha ido y todavía no vieron la necesidad de proporcionar un std::tree , aunque surgió la idea (ver aquí ). Quizás la razón por la que no han agregado esto es que es trivialmente fácil construir uno propio sobre los contenedores existentes. Por ejemplo…

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

Un cruce simple usaría la recursión …

 template< typename T > void tree_node::walk_depth_first() const { cout< 

Si desea mantener una jerarquía y desea que funcione con algoritmos STL , entonces las cosas pueden complicarse. Puede construir sus propios iteradores y lograr cierta compatibilidad, sin embargo, muchos de los algoritmos simplemente no tienen ningún sentido para una jerarquía (cualquier cosa que cambie el orden de un rango, por ejemplo). Incluso la definición de un rango dentro de una jerarquía podría ser un asunto complicado.

Si está buscando una implementación de RB-tree, stl_tree.h puede ser apropiado para usted también.

std :: map se basa en un árbol negro rojo . También puede usar otros contenedores para ayudarlo a implementar sus propios tipos de árboles.

En cierto modo, std :: map es un árbol (se requiere que tenga las mismas características de rendimiento que un árbol binario equilibrado) pero no expone otras funciones de árbol. El posible razonamiento detrás de no incluir una estructura de datos de árbol real probablemente fue solo una cuestión de no incluir todo en el stl. El stl se puede ver como un marco para usar en la implementación de sus propios algoritmos y estructuras de datos.

En general, si hay una funcionalidad de biblioteca básica que desea, eso no está en el stl, la solución es mirar BOOST .

De lo contrario, hay un montón de bibliotecas , dependiendo de las necesidades de su árbol.

Todos los contenedores STL se representan externamente como “secuencias” con un mecanismo de iteración. Los árboles no siguen este modismo.

Porque el STL no es una biblioteca de “todo”. Contiene, esencialmente, las estructuras mínimas necesarias para construir cosas.

Este parece prometedor y parece ser lo que estás buscando: http://tree.phi-sci.com/

OMI, una omisión. Pero creo que hay buenas razones para no incluir una estructura de árbol en el STL. Hay una gran cantidad de lógica en el mantenimiento de un árbol, que se escribe mejor como funciones miembro en el objeto base TreeNode . Cuando TreeNode está envuelto en un encabezado STL, simplemente se vuelve más complicado.

Por ejemplo:

 template  struct TreeNode { T* DATA ; // data of type T to be stored at this TreeNode vector< TreeNode* > 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  struct Tree { TreeNode* root; // TREE LEVEL functions void clear() { delete root ; root=0; } void insert( T* data ) { if(root)root->insert(data); } } ; 

Creo que hay varias razones por las cuales no hay árboles stl. Principalmente, los árboles son una forma de estructura de datos recursiva que, como un contenedor (lista, vector, conjunto), tiene una estructura fina muy diferente que hace que las decisiones correctas sean complicadas. También son muy fáciles de construir en forma básica utilizando el STL.

Se puede considerar que un árbol de raíz finita es un contenedor que tiene un valor o carga útil, por ejemplo, una instancia de una clase A y una posible colección vacía de árboles (sub) enraizados; los árboles que están vacíos de subárboles se consideran como hojas.

 template struct unordered_tree : std::set, A {}; template struct b_tree : std::vector, A {}; template struct planar_tree : std::list, A {}; 

Uno tiene que pensar un poco en el diseño de iteradores, etc. y qué operaciones de productos y coproductos uno permite definir y ser eficiente entre árboles, y el stl original debe estar bien escrito, de modo que el contenedor vacío del conjunto, vector o lista sea realmente vacío de cualquier carga útil en el caso predeterminado.

Los árboles desempeñan un papel esencial en muchas estructuras matemáticas (véanse los documentos clásicos de Butcher, Grossman y Larsen, y también los documentos de Connes y Kriemer para ver ejemplos de cómo se pueden unir y cómo se usan para enumerar). No es correcto pensar que su papel es simplemente facilitar ciertas otras operaciones. Más bien facilitan esas tareas debido a su papel fundamental como estructura de datos.

Sin embargo, además de los árboles, también hay “co-árboles”; los árboles sobre todo tienen la propiedad de que si eliminas la raíz, borras todo.

Considere iteradores en el árbol, probablemente se realizarían como una simple stack de iteradores, a un nodo, y a su padre, … hasta la raíz.

 template struct node_iterator : std::stack{ operator*() {return *back();} ...}; 

Sin embargo, puedes tener tantos como quieras; colectivamente forman un “árbol”, pero donde todas las flechas fluyen en la dirección hacia la raíz, este co-árbol puede iterar a través de iteradores hacia el iterador trivial y la raíz; sin embargo, no se puede navegar a través o hacia abajo (no se conocen los otros iteradores) ni se puede eliminar el conjunto de iteradores, excepto haciendo un seguimiento de todas las instancias.

Los árboles son increíblemente útiles, tienen mucha estructura, esto hace que sea un desafío serio obtener el enfoque definitivamente correcto. En mi opinión, esta es la razón por la cual no se implementan en el STL. Además, en el pasado, he visto personas que se vuelven religiosas y encuentran desafiante la idea de que un tipo de contenedor que contenga instancias de su propio tipo -pero tienen que enfrentarlo- eso es lo que representa un tipo de árbol: es un nodo que contiene un posiblemente una colección vacía de árboles (más pequeños). El lenguaje actual lo permite sin problemas al proporcionar el constructor predeterminado para el container no asigna espacio en el montón (o en otro lugar) para un B , etc.

Por mi parte, estaría contento si esto, en una buena forma, encontrara su camino hacia el estándar.

Todos los contenedores STL se pueden usar con iteradores. No se puede hacer que un iterador sea un árbol, porque no se tiene el camino “uno a la derecha”, sí se pasa por el árbol.