Not logged in, Join Here! or Log In Below:  
News Articles Search    

 Home / General Programming / balancing an stl::map Account Manager
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
Nils Pipenbrinck

March 15, 2005, 07:30 AM

I have a stl map that maps strings to other things. I assume that the map uses a binary tree internally (correct me if I'm wrong here)

If I would insert some strings that are already ordered I will end up with a worst case, unbalanced tree, and my searches would take longer than nessesary.

Is there some simple way to balance a map after it was built? I don't mind if it takes some time, I do that at load time.



March 15, 2005, 07:33 AM

If I'm not totally mistaken, std::map uses a red-black-tree and stays balanced.

Did you verify that the degenerate case actually appears, or is it a (justified) fear only ?


March 15, 2005, 07:37 AM

Chris is right. You don't need to balance a std::map.

Nils Pipenbrinck

March 15, 2005, 11:52 AM

cool. I haven't noticed any speed differences, I was just curious how to do it if I have to do it..


This thread contains 4 messages.
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.