¿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 ...
373
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
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
stl::red_black_treeetc. Finalmente, los árboles std::mapy std::setestán equilibrados, un std::treepodría no serlo.
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:
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:
std::map, no llamaría a esos contenedores de árbol. Esos son contenedores asociativos que comúnmente se implementan como árboles. Gran diferencia.
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.
end()y begin()con el que puedes recorrer todos los elementos, etc.
begin()y end()). Y recuerde que una cola prioritaria suele ser un montón, que al menos en teoría es un árbol (aunque las implementaciones reales). Por lo tanto, incluso si implementara un árbol como adaptador utilizando alguna estructura de datos subyacente diferente, sería elegible para ser incluido en el STL.
"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.
many of the algorithms simply don't make any sense for a hierarchy. Una cuestión de interpretación. Imagine una estructura de usuarios de stackoverflow y cada año desea que aquellos con una mayor cantidad de puntos de reputación lideren a aquellos con puntos de reputación más bajos. Proporcionando así un iterador BFS y una comparación adecuada, cada año que acaba de ejecutar std::sort(tree.begin(), tree.end()).
vectorcon mapen el ejemplo anterior. Para un soporte completo de una estructura similar a JSON, puede usar variantpara definir los nodos.
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.
ordered red-black tree of {key, mapped} values, unique keysclase interna , definida en <xtree>. No tengo acceso a una versión más moderna en este momento.
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.
std::mapse implementa internamente como btree, pero externamente aparece como una SECUENCIA ordenada de PARES. Dado cualquier elemento que pueda preguntar universalmente quién es antes y quién es después. Una estructura de árbol general que contiene elementos, cada uno de los cuales contiene otros, no impone ningún orden o dirección. Puede definir iteradores que recorran una estructura de árbol de muchas maneras (sallow | deep first | last ...) pero una vez que lo hizo, un std::treecontenedor debe devolver uno de ellos de una beginfunción. Y no hay una razón obvia para devolver uno u otro.
std::unordered_set, que no tiene una "forma única" de iterar sus miembros (de hecho, el orden de iteración es pseudoaleatorio y la implementación está definida), pero sigue siendo un contenedor stl; esto refuta su punto. Iterar sobre cada elemento en un contenedor sigue siendo una operación útil, incluso si el orden no está definido.
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.
s, por ejemplo, se podría iterar sobre los nodos como s000, s00, s001, s0, s010, s01, s011, s, s100, s10, s101, s1, s110, s11, s111(" más a la izquierda" a 'más a la derecha'), sino que también podría utilizar un patrón de profundidad de recorrido ( s, s0, s1, s00, s01, s10, s11,
std::unordered_setse "hizo" una secuencia porque no conocemos una mejor manera de iterar sobre los elementos que no sea una forma arbitraria (dada internamente por la función hash). Creo que es el caso opuesto del árbol: la iteración sobre unordered_setestá subespecificada, en teoría "no hay forma" de definir una iteración que no sea "al azar". En el caso del árbol hay muchas formas "buenas" (no aleatorias). Pero, nuevamente, su punto es válido.
std::unordered_mapystd::unordered_sethasta hace poco. Y antes de eso no había contenedores STL en la biblioteca estándar.std::mapystd::setusaré un árbol en cada implementación, pero no tienen que hacerlo si alguna estructura que no sea un árbol también cumple con las especificaciones.