Internal implementation of STL :: MAP in C ++

Question

I wanted to know how MAP is available in C ++, not MultiMap just a simple map implemented internally.

What I can best think of:

For Integer Mapping: A Balanced Binary Search Tree could be used .

For String Mapping: Compressed Trie or something similar could be used .

I'm really curious how this is implemented on an STL card. Is any hash function being used or is it something completely different from this.

Answer 1

Ordered containers, including std::map , are implemented as balanced binary trees (usually RB trees, but any other balanced tree meets the requirements).

For this type of question, the most important part of the required information is the complexity requirements for each of the operations in the container, which complies with the standard. This is also the most important answer, that is, as long as the complexity requirements are met, the actual implementation does not matter much.