español - ¿Por qué el C++ STL no proporciona ningún contenedor de "árbol"?
stl c++ español (13)
¿Por qué el C ++ STL no proporciona ningún contenedor de "á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 ...
"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 surgió la idea (ver here ). Quizás la razón por la que no han agregado esto es que es trivialmente fácil construir el suyo 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 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.
Creo que hay varias razones por las que 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 de raíz finita se puede considerar como un contenedor que tiene un valor o una carga útil, por ejemplo, una instancia de una clase A y, posiblemente, una colección vacía de árboles (sub) enraizados; 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 permite definir y ser eficiente entre los árboles, y el stl original debe estar bien escrito, de modo que el conjunto vacío, vector o contenedor de lista sea realmente vacío de cualquier carga útil en el caso por defecto.
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-á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, para un nodo, y para 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 (no se conocen los otros iteradores) 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, esto hace que sea un desafío serio obtener el enfoque correcto definitivo. En mi opinión, es por eso que no están implementados en la 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 el container<B> no asigna espacio en el montón (o en cualquier otro lugar) para una B , etc.
Por mi parte, me encantaría que esto, en buena forma, encontrara su camino hacia el estándar.
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 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 bunch de libraries out there , dependiendo de las necesidades de su árbol.
Este parece prometedor y parece ser lo que estás buscando: http://tree.phi-sci.com/
Hay dos razones por las que podrías querer usar un árbol:
Desea reflejar el problema utilizando una estructura similar a un árbol:
Para ello disponemos de biblioteca de gráficos de impulso.
O quieres un contenedor que tenga características de acceso tipo árbol. Para esto tenemos
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 de árbol C
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 miembro para el acceso. Su código no está vinculado a cómo se implementa el contenedor, sino a qué tan rápido es, si tiene un ordenamiento fijo y definido, o si es eficiente en el espacio, y así sucesivamente.
OMI, una omisión. Pero creo que hay una buena razón 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 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); }
} ;
Porque el STL no es una librería de "todo". Contiene, esencialmente, las estructuras mínimas necesarias para construir cosas.
Probablemente por la misma razón que no hay ningún contenedor de árboles en impulso. Hay muchas maneras 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, ¿necesitas 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í están algunas otras implementaciones de árbol genérico:
- El árbol de Kasper Peeters.
- bosque de adobe
- core::tree
Si está buscando una implementación de árbol RB, entonces stl_tree.h podría ser apropiado para usted.
Todos los contenedores STL se pueden utilizar con iteradores. No puede tener un iterador y un árbol, porque no tiene la forma "correcta" de atravesar el árbol.
Todos los contenedores de STL se representan externamente como "secuencias" con un mecanismo de iteración. Los árboles no siguen este lenguaje.
el std :: map se basa en un árbol negro rojo . También puede usar otros containers para ayudarlo a implementar sus propios tipos de árboles.