Difference between std :: map, std :: unordered_map, std :: flat_map, and which one to choose?

Performance is relative. Performance in what? In access? In insertion? What is the use of performance if the structure does not do what it needs?

If you need a map with a defined order, you can not use a unordered_map .

If you need flat_map and you can only use the default library, as the question shows, there is no way that it is not already available in it. Typically staff uses the Boost implementation .

The ordered map structure performs very well in almost all operations, but an unordered map can be faster in most cases, although it has no good warranties and in the worst case (very rare, almost impossible in practice) can be extremely slow (allows even DOS attack).

A ( ordered ) map is usually implemented with a binary search tree and unordered_map is usually a Spreading table .

flat_map is usually a tree implemented over an array , which prevents certain guarantees in some operations (it may be slow to insert a new element when the structure is full, and not automatically decreases in size if possible), but it allows some gains in access, and may even have the best possible performance depending on how you need the data and how it is organized. Linear access is usually great. The insert may have gained if it is also linear. Gains do not occur in any set of data, it can even get worse.

Finally this structure is good for very rare cases where it is known that the data is very linear, which would almost always allow the use of another structure, perhaps even a Vector .