¿Por qué el STL de C ++ no proporciona ningún contenedor de "árbol"?

¿Por qué el STL de C ++ no proporciona ningún contenedor de "árbol", y cuál es la mejor opción?

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

Hay dos razones por las que podrías 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 desea un contenedor que tenga características de acceso tipo árbol. Para esto tenemos

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

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

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

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

Algunas cuestiones a tener en cuenta:

• ¿El número de hijos para un nodo es fijo o variable?
• ¿Cuánta sobrecarga por nodo? - es decir, ¿necesita punteros para padres, punteros para hermanos, etc.
• ¿Qué algoritmos proporcionar? - diferentes iteradores, 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 para qué podría usarse una biblioteca de árbol.

Aquí hay algunas otras implementaciones de árbol genéricas:

• El árbol de Kasper Peeters.hh
• Bosque de adobe
• núcleo :: árbol

La filosofía de STL es que elija un contenedor basado en garantías y no en cómo se implementa 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 todos modos, estás usando iteradores o funciones miembro para el acceso. Su código no está vinculado a cómo se implementa el contenedor, sino a qué tan rápido es, 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 vino y se fue y todavía no vieron la necesidad de proporcionar un std::tree, aunque la idea surgió (ver aquí ). Tal vez 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<tree_node> children;
   };

Un recorrido simple usaría la recursividad ...

template< typename T >
void tree_node<T>::walk_depth_first() const
   {
   cout<<t;
   for ( auto & n: children ) n.walk_depth_first();
   }

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

Si está buscando una implementación de árbol RB, entonces stl_tree.h podría ser apropiado para usted también.

El mapa std :: 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 otra funcionalidad de árbol. El probable 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 puede verse 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, que no está en el stl, la solución es mirar BOOST .

De lo contrario, hay un montón de bibliotecas a cabo allí , 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 idioma.

Porque el STL no es una biblioteca "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 mucha lógica en el mantenimiento de un árbol, que se escribe mejor como funciones miembro en el TreeNodeobjeto base . Cuando TreeNodeestá envuelto en un encabezado STL, simplemente se vuelve más desordenado.

Por ejemplo:

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

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 dificulta las elecciones correctas. También son muy fáciles de construir en forma básica utilizando el STL.

Un árbol enraizado finito puede considerarse como un contenedor que tiene un valor o carga útil, digamos una instancia de una clase A y, una colección posiblemente vacía de (sub) árboles enraizados; Los árboles con una colección vacía de árboles se consideran hojas.

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

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

Los árboles juegan un papel esencial en muchas estructuras matemáticas (véanse los documentos clásicos de Butcher, Grossman y Larsen; 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, eliminas todo.

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

template<class TREE>
struct node_iterator : std::stack<TREE::iterator>{
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 iterarse 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 conoce a los otros iteradores) ni se puede eliminar el conjunto de iteradores excepto si se realiza 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, es por eso que no se implementan en el STL. Además, en el pasado, he visto a personas volverse religiosas y encontrar desafiante la idea de un tipo de contenedor que contiene 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 colección vacía de árboles (más pequeños). El lenguaje actual lo permite sin problemas, ya que el constructor predeterminado container<B>no asigna espacio en el montón (ni en ningún otro lugar) para un B, etc.

Por mi parte, estaría satisfecho si esto, en buena forma, llegara a la norma.

Leyendo las respuestas aquí, las razones comunes nombradas son que uno no puede recorrer el árbol o que el árbol no asume la interfaz similar a otros contenedores STL y que uno no puede usar algoritmos STL con dicha estructura de árbol.

Teniendo eso en mente, traté de diseñar mi propia estructura de datos de árbol que proporcionará una interfaz similar a STL y será utilizable con los algoritmos STL existentes tanto como sea posible.

Mi idea era que el árbol debe basarse en los contenedores STL existentes y que no debe ocultar el contenedor, de modo que sea accesible para usar con algoritmos STL.

La otra característica importante que debe proporcionar el árbol son los iteradores de desplazamiento.

Esto es lo que pude encontrar: https://github.com/igagis/utki/blob/master/src/utki/tree.hpp

Y aquí están las pruebas: https://github.com/igagis/utki/blob/master/tests/tree/tests.cpp

Todos los contenedores STL se pueden usar con iteradores. No puede tener un iterador y un árbol, porque no tiene una forma '' correcta '' de atravesar el árbol.