STL-карта, где реализована _Rb_tree_insert_and_rebalance?

Я смотрел, как реализован STL std::map. Я знал, что он реализован с использованием красных черных деревьев. Таким образом, мне просто было интересно узнать, как Красные Черные Деревья внедрены в STL из-за того, что они знают, насколько эффективна реализация.STL-карта, где реализована _Rb_tree_insert_and_rebalance?

std::map содержит stl_tree.h. Здесь используется Red Black Tree.

Все функции (там, где выполняется вставка) абстрактно ввод и звонки _Rb_tree_insert_and_rebalance функция. Но я не смог найти реализацию этого.

Любые идеи, где это реализовано?

источник

2013-05-31 Srinath G S

Если по STL вы имеете в виду стандартную библиотеку C++ (как предложено пространством имен std), то это зависит исключительно от реализации. Поэтому вы должны уточнить, какую стандартную библиотечную реализацию вы имеете в виду. Если вы действительно имеете в виду STL, тогда в нем нет 'std :: map' (просто' map'). – juanchopanza

Это полномасштабная реализация, однако, я думаю, вы имеете в виду libstdc++, поэтому, поскольку реализация является открытым исходным кодом - вы можете искать эту функцию в исходных файлах. В gcc-4.8 эта функция находится в файле libstdc++-v3/src/c++98/tree.cc. Например, вы можете найти его здесь: github gcc sources

источник

2013-05-31 09:09:31 ForEveR

Спасибо. Я просматривал gcc-пакеты, доступные в каталоге установки, и не мог найти это. –

Просто примечательное примечание: формально это не реализация, так как в определении языка говорится, что «определенный реализацией» означает, что соответствующая реализация должна документировать, что она делает. Это, однако, конкретная реализация. –

@PeteBecker спасибо, обновлено. – ForEveR

STL-карта, где реализована _Rb_tree_insert_and_rebalance?

ответ

Смежные вопросы