underlying implementation for std map

Bvm 18
Bvm 18 used Ask the Experts™
Hi all,

  std map uses red-black or avl tree in C++?

  where can I find underlying implementation of std map? Is it depended on compilers?

Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
nociSoftware Engineer
Distinguished Expert 2018

I guess in the stdc++ sources for GCC can be referenced for this

Mihai BarbosTrying to tame bits. They're nasty.

Red-black, from what I know. But it can be that some implement it in different way (most likely AVL)
This is not really compiler dependent, it depends on the C++ library (which comes with the compiler ;)
nociSoftware Engineer
Distinguished Expert 2018

All reference is have seen now are red-black balanced tree.
And it may be depending on compilers.
How to Generate Services Revenue the Easiest Way

This Tuesday! Learn key insights about modern cyber protection services & gain practical strategies to skyrocket business:

- What it takes to build a cloud service portfolio
- How to determine which services will help your unique business grow
- Various use-cases and examples

evilrixSenior Software Engineer (Avast)

It isn't defined in the C++ standard and is implementation specific. Most use a red/black tree, but you cannot depend on this.


where can we find the C++ standard documentation for std::map?

And, what are the implementations done std::map under gcc, msvc compilers for C++98/11/14/17?
This link will give you the links on how to obtain the several standards that are available for a price. It also gives working draft links that are available at no cost.
Here is a link for one of the map functions. It has two tabs for availability since 98 and 11.


On the bottom left pane is a list of all the functions available with a notation of C++11 for functions introduced in that standard.
>> std::map under gcc, msvc compilers for C++98/11/14/17?

Here is one way to get the implementations. I would write a  small main program using map.

With a good IDE you can specify the standard you want to look at. Then right click on the #include <map> statement and go to its header. Save that header locally with the version notation. Then change the IDE to use a different standard and then get a different map header file.

Alternatively, you can build the program using different standards. With g++ to get 11, add the option -std=c++11.
Without that option you are getting C++03, which fixes the issues in C++98. Now you can run the GDB debugger and step into the map function to actually see the header file implementation.
evilrixSenior Software Engineer (Avast)

You can find every C++ standards doc here:


Follow the instructions on the page to access each doc (it's pretty simple).

Note, these are the final drafts, but are pretty much identical to the final release (which you have to pay for).

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial