¿Por qué la C ++ STL no proporciona ningún & # 8220; tree & # 8221; contenedores?

Question

¿Por qué el C ++ STL no proporciona ningún " árbol " contenedores, 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 ...

Answer 1

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 aumentar la biblioteca de gráficos

O quieres un contenedor que tenga características de acceso tipo árbol Para ello 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 deben implementarse utilizando árboles (aunque esto no es realmente un requisito).

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

Answer 2

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

Algunos temas a considerar:
 - ¿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 lo que podría usarse una biblioteca de árbol.

Aquí hay otras implementaciones de árbol genérico:
 - árbol de Kasper Peeters.hh
 - bosque de Adobe
 - core :: tree

Answer 3

La filosofía de STL es que usted elige 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. Para cualquier cosa que te importe, el contenedor puede implementarse como una lista unidireccional, siempre que la búsqueda sea muy rápida, estarás contento. Esto se debe a que, de todos modos, no está tocando las partes internas, está utilizando iteradores o funciones de 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 una ordenación fija y definida, o si es eficiente en el espacio, etc. ».

Answer 4

  

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

C ++ 11 vino y se fue y aún no vieron la necesidad de proporcionar un std :: tree , aunque surgió la idea (consulte aquí ). Tal vez la razón por la que no han agregado esto es que es trivialmente fácil construir tu propio encima de los contenedores existentes. Por ejemplo ...

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

Un recorrido simple usaría recursión ...

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 , entonces las cosas pueden complicarse. Podría crear 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 definir un rango dentro de una jerarquía podría ser un negocio desordenado.

Answer 5

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

Answer 6

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

Answer 7

En cierto modo, std :: map es un árbol (se requiere que tenga las mismas características de rendimiento que un árbol binario balanceado) pero no expone otra funcionalidad de árbol. El posible razonamiento detrás de no incluir una estructura de datos de árbol real fue probablemente 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 grupo de bibliotecas out allí , dependiendo de las necesidades de tu árbol.

Answer 8

Todos los contenedores de STL se representan externamente como " secuencias " Con un mecanismo de iteración. Los árboles no siguen este lenguaje.

Answer 9

Porque el STL no es un " todo " biblioteca. Contiene, esencialmente, las estructuras mínimas necesarias para construir cosas.

Answer 10

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

Answer 11

OMI, una omisión. Pero creo que hay una buena razón para no incluir una estructura de árbol en la STL. Hay mucha lógica en el mantenimiento de un árbol, que se escribe mejor como funciones miembro en el objeto TreeNode base . Cuando TreeNode está 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); } 
} ;

Answer 12

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 la STL.

Un árbol con raíces finitas puede considerarse como un contenedor que tiene un valor o una carga útil, por ejemplo, una clase de A y una colección posiblemente vacía de (sub) árboles con raíces; Los árboles que se vacían de subárboles se consideran como 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 producto y coproducto permiten definir y ser eficientes entre los árboles, y el stl original debe estar bien escrito, de modo que el conjunto vacío, el vector o El contenedor de la lista está 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; también los documentos de Connes y Kriemer para ver ejemplos de cómo se pueden unir y cómo se utilizan para enumerar). No es correcto pensar que su función es simplemente facilitar 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-trees " ;; 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 árbol paralelo 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 (los otros iteradores no lo conocen) ni se puede eliminar el conjunto de iteradores excepto mediante el seguimiento de todas las instancias.

Los árboles son increíblemente útiles, tienen mucha estructura, lo que hace que sea un desafío serio obtener el enfoque definitivo correcto. En mi opinión, es por eso que no están implementados en el STL. Además, en el pasado, he visto a personas que se vuelven religiosas y encuentran que la idea de un tipo de contenedor que contiene instancias de su propio tipo es desafiante, 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 idioma actual lo permite sin problemas, ya que el constructor predeterminado para container < B > no asigna espacio en el montón (o en cualquier otro lugar) para un B , etc.

Por mi parte, me encantaría que esto, en buena forma, se haya introducido en el estándar.

Answer 13

Todos los contenedores STL pueden usarse con iteradores. No puedes tener un iterador y un árbol, porque no tienes la manera "correcta" de atravesar el árbol.