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

Asked

Viewed 194 times

2

What is the difference between library functions map, unordered_map, flat_map, and which one to use, for example in terms of performance?

c++ performance hashmap map

  • You may be useful: https://stackoverflow.com/questions/21166675/boostflat-map-and-its-performance-compared-to-map-and-unorderedmap

  • Did the answer resolve what was in doubt? Do you need something else to be improved? Do you think it is possible to accept it now?

  • Yes, took away my doubt, just forgot to click the button to accept the answer, sorry for that, one thing about the boost library, their functions compared to Std library are faster?

  • @cYeR has no way to state it in general. Boost is increasingly unnecessary in most scenarios.

1 answer

2


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

If you need a map with defined order you cannot use a unordered_map.

If you need the flat_map and you can only use the standard library, as the question shows, as it is already not available in it. In general the staff uses the implementation of Boost.

The ordered map structure has very good performance in almost every operation, but an unordered map can be faster in most cases, although it has no good guarantees and in the worst case (very rare, almost impossible in practice) can be extremely slow (even allows attack of DOS).

To (ordered) map is usually implemented with a binary search tree and the unordered_map used to be a scattering table.

To flat_map is usually a tree implemented on top of a array, which prevents certain guarantees in some operations (it may be slow to insert a new element when the structure is full, and also does not automatically decrease in size if possible), but allows some gains in access, may even have the best possible performance depending on how accurate the data is and how it is organized. Linear access is usually great. Insertion may have gained if it is also very linear. Winnings do not occur in any data set, it may even get much worse.

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

Browser other questions tagged c++ performance hashmap map

You are not signed in. Login or sign up in order to post.