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

4

I know that every element of the structure is represented by a key and a given, but I do not see it as a tree, and I read somewhere that it is a tree.

    
asked by anonymous 15.09.2016 / 22:31

3 answers

4

std::map is likely to be done with a tree. There are no warranties.

The specification does not say 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 be free to do as it sees fit.

When you are going to use a map it only matters that it is a map, that is, it is a collection of data with key and value pairs sorted by the 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 way that works best for elements that can be inserted in any order and access must be classified. There are several possible tree variations that each implementer can choose.

A implementation example .

You have an article that says the implementation originally used in STL is < a href="https://en.wikipedia.org/wiki/Red%E2%80%93black_tree"> Red Black Tree . Modern libraries are likely to use variations of this.

    
15.09.2016 / 22:38
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".

Stackoverflow article in English on the subject: link

    
15.09.2016 / 22:37
2

Yes, MAP implementations are usually done using binary search trees (not just in C ++). Even in link site has good references, and it has this short comment about std :: map:

  

Maps are typically implemented as binary search trees. MAP Link

    
16.09.2016 / 18:32