Search code examples
c++dictionaryred-black-tree

STL Map where is _Rb_tree_insert_and_rebalance implemented?

I was looking through how the STL std::map is implemented. I knew that it is implemented using Red Black Trees. So, I just was curious to know how Red Black Trees are implemented in STL for reasons of knowing how efficient the implementation is.

std::map includes stl_tree.h. This is where the Red Black Tree is implemented.

All the functions (where insert takes place) abstract the insertion and calls _Rb_tree_insert_and_rebalance function. But I could not find the implementation of this.

Any ideas where it is implemented?

Solution

  • It's fully implementation-specific, however, I think you mean libstdc++, so, since realization is open-source - you can search for this function in source files. In gcc-4.8 this function is in file libstdc++-v3/src/c++98/tree.cc. For example you can search it here: github gcc sources