Is the Std::map structure in C++ a tree?

Question

I know that every element of the structure is represented by a key and a datum, but I don’t see it as a tree, and I read somewhere that it’s a tree.

Answer 1

It is quite likely that the std::map be done with a tree. No guarantees.

To specification does not tell how it should be implemented and should not even determine implementation detail. It is the function of the specification to say that public guarantees an implementation should give and nothing else. Each implementation should have the freedom to do as it sees fit.

When using a map it only matters that it is a map, that is, it is a collection of data with key pairs and value sorted by key.

If you stick to the implementation you may have problems when it is not available.

A tree is a good implementation for this problem because it is the form that usually works best for elements that can be inserted in any order and the access must be classified. There are several possible tree variations that each implementer can choose.

A example of implementation.

Has a article that says the implementation originally used in STL is the Red Black Tree. It is quite likely that modern libraries use variations of this.

Answer 2

The C++ definition does not specify how the implementation should be done. However, the most common implementation seems to be a "red black Tree".

Article in Stackoverflow on the subject: https://stackoverflow.com/questions/5288320/why-is-stdmap-implemented-as-a-red-black-tree

Answer 3

Yes, generally Maps implementations are done using binary search trees (not only in c++). Including on the website http://www.cplusplus.com/ has good references, and she has this little comment about Std::map:

Maps are typically implemented as Binary search Trees.Link to the MAP