RTFSC

[ Read The F***ing Source Code – allegedly from a very famous IT guy ]

When I wanted to find out how the “map”, which is an associative container, is implemented in C++ STL, things were not going well. I got some information from Internet that map is implemented by red-black tree, but none of wikipedia, Microsoft or www.cplusplus.com confirms it. They just said that “map” is a sorted associative array.

After I did some research on this topic, I confirmed that all informations are right. C++ STL did not define the implementation of “map”. Therefore, C++ compilers and C++ libraries could have their own implementations. In general, all balanced trees are satisified to implement “map”.

After going through the SGI STL source code (http://www.sgi.com/tech/stl/), one thing is sure: “map” in SGI STL is implemented by redblack tree.