What data structure is inside std map in C

Question

I'm a beginner learning C++. I'm having trouble understanding std::map concepts because the code I'm playing with implies that the map is a search tree, i.e. all std::map object names contain *tree as well as comments.

Answer 1

An associative container is std::map.

The standard's only requirement is that the container have an associative container interface and behaviour; however, the implementation is not specified.

The implementation is valid, as long as it meets the complexity and interface requirements.

std::map, on the other hand, is typically implemented with a red-black tree.