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

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

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

Desea reflejar el problema utilizando una estructura en forma de árbol:
Para esto tenemos la biblioteca de gráficos Boost

O quieres 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 deben implementarse utilizando árboles (aunque esto no es un requisito).

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


Probablemente por la misma razón por la que no hay un contenedor de árboles en Boost. Hay muchas formas de implementar un contenedor de este tipo, y no hay una buena manera de satisfacer a todos los que lo utilizarían.

Algunas cuestiones a tener en cuenta:

  • ¿El número de elementos secundarios de 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 árboles 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 lo que podría usarse una biblioteca de árboles.

Aquí hay algunas otras implementaciones de árboles genéricos:

  • Árbol de Kasper Peeters.hh
  • Bosque de Adobe
  • núcleo::árbol

La filosofía de STL es que elige un contenedor en función de las garantías y no en función de cómo se implementa el contenedor. Por ejemplo, su elección de contenedor puede basarse en la necesidad de búsquedas rápidas. Para todo lo que le interese, el contenedor puede implementarse como una lista unidireccional, siempre que la búsqueda sea muy rápida, estarí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á ligado 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, etc.