Uso de la implementación interna de STL del árbol rojo-negro

Question

Entiendo que mi STL (que viene con g ++ 4.x.x) utiliza árboles rojo-negro para implementar contenedores como el mapa. ¿Es posible usar directamente el árbol rojo-negro interno de STL? ¿Si es así, cómo? Si no, ¿por qué no? ¿Por qué STL no expone el árbol rojo-negro?

Sorprendentemente, no puedo encontrar una respuesta usando Google.

Editar: Estoy investigando el uso del árbol rojo-negro como una solución a la inserción de llamada del constructor extra allocator. Ver this question. Mi STL usa árboles rojo-negro para la implementación del mapa.

Answer 1

En realidad, la respuesta es muy simple e independiente de su versión de gcc. Puede descargar el código fuente stl desde sgi's website y ver la implementación y el uso por usted mismo.

Por ejemplo, en la versión 3.2, puede ver la implementación del árbol rojo-negro en el archivo stl_tree.h, y un ejemplo de su uso en stl_set.h.

Tenga en cuenta que dado que las clases stl son clases de plantilla, las implementaciones están realmente dentro de los archivos de encabezado.

Answer 2

mayoría de las implementaciones de STL set y map son árboles negros rojos creo, aunque nada impide que alguien de su aplicación utilizando una estructura de datos diferente - si no recuerdo mal, el estándar de C++ no requiere una implementación árbol de RB.

El STL no lo expone porque eso violaría los principios de OOP ... exponer la estructura de datos subyacente podría conducir a un comportamiento no deseado si alguien más fuera a usar su biblioteca. Es decir, específicamente para set y map, solo se le debe permitir el acceso a métodos que se ajusten a las estructuras de datos set y map ... exponer la representación subyacente podría llevar a un usuario a tener duplicados dentro de set, lo cual es malo.

Dicho esto, no hay forma (que yo sepa) de usar directamente el árbol rojo negro subyacente ... dependería mucho de cómo quisiera usarlo. La implementación de su propio árbol rojo-negro sería su mejor opción, o consulte nuestras bibliotecas de terceros (¿tal vez Boost?)

Answer 3

Ni siquiera se le garantiza que la estructura de datos utilizada sea sea una red- árbol negro (por ejemplo, se ha implementado al menos una vez como un árbol AVL, y algo así como B-, B * o árbol B + probablemente también estaría bien).

Como tal, la única manera de acceder a las partes internas sería observar una implementación específica, y hacer uso de cosas que no (al menos intentar) exponer públicamente.

En cuanto al por qué: creo que principalmente porque es un intento de abstracción, sin exponer todos los detalles de implementación.