Использование внутренней реализации красно-черного дерева в STL
Я понимаю, что мой STL (который поставляется с g++ 4.xx) использует красно-черные деревья для реализации контейнеров, таких как карта. Можно ли использовать внутреннее красно-черное дерево STL напрямую. Если так, то как? Если нет, то почему нет - почему STL не выставляет красно-черное дерево?
Удивительно, но я не могу найти ответ с помощью Google.
Редактировать: я исследую использование красно-черного дерева в качестве решения для дополнительного вызова конструктора распределителя при вставке. Смотрите этот вопрос. Мой STL использует красно-черные деревья для реализации карты.
3 ответа
На самом деле - ответ очень прост и не зависит от вашей версии gcc. Вы можете скачать исходный код stl с веб-сайта sgi, а также ознакомиться с его реализацией и использованием.
Например, в версии 3.2 вы можете увидеть реализацию красно-черного дерева в файле stl_tree.h и пример ее использования в stl_set.h.
Обратите внимание, что поскольку классы stl являются шаблонными классами, реализации фактически находятся внутри заголовочных файлов.
Большинство реализаций STL set а также map Я считаю, что это красные чёрные деревья, хотя ничто не мешает кому-то реализовать их, используя другую структуру данных - если я правильно помню, стандарт C++ не требует реализации дерева RB.
STL не раскрывает его, поскольку это нарушит принципы ООП. Обнародование базовой структуры данных может привести к нежелательному поведению, если кто-то другой будет использовать вашу библиотеку. То есть специально для set а также map, вы должны иметь доступ только к методам, которые соответствуют set а также map структуры данных... раскрытие основного представления может привести к тому, что у пользователя будут дубликаты внутри set, что плохо.
Тем не менее, нет никакого способа (насколько мне известно) напрямую использовать лежащее в основе красное черное дерево... это будет во многом зависеть от того, как вы захотите его использовать. Реализация вашего собственного красно-черного дерева, скорее всего, будет вашим лучшим выбором, или проверьте наши сторонние библиотеки (возможно, Boost?)
Вам даже не дают гарантии, что используемой структурой данных будет красно-черное дерево (например, оно было реализовано хотя бы один раз как дерево AVL, и что-то вроде дерева B-, B* или B+, вероятно, будет хорошо Что ж).
Таким образом, единственный способ получить доступ к внутренним компонентам - это посмотреть на конкретную реализацию и использовать вещи, которые она (по крайней мере, не пытается) обнародовать.
Что касается того, почему: я думаю в основном потому, что это попытка абстрагирования, а не раскрытие всех деталей реализации.