title: STL Map where is _Rb_tree_insert_and_rebalance implemented?
body: <p>I was looking through how the STL <code>std::map</code> 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. </p>
  
  <p><code>std::map</code> includes <code>stl_tree.h</code>. This is where the Red Black Tree is implemented.</p>
  
  <p>All the functions (where insert takes place) abstract the insertion and calls <code>_Rb_tree_insert_and_rebalance</code> function. But I could not find the implementation of this.</p>
  
  <p>Any ideas where it is implemented?</p>