On the other hand, std::map uses a binary tree (which is ordered) for storing the data. |
The implementation of STL containers is not specified in the standard. See
http://en.cppreference.com/w/cpp/container/map
cppreference wrote: |
---|
Maps are usually implemented as red-black trees. |
Edit []
There are several other considerations: Move semantics, cache effects, [concurrency,] the sorting algorithm
Basically the only real way to find out, is to test with varying amounts of data, you might have to go into the tens of millions of items before you get one out performing the other. In the past I have been surprised about how well std::vector performs versus other containers. For example,
up to a point vector performed better than std::unordered_map, and that included initializing
and sorting,
and finding. IIRC I had to have about 8 million items before std::unordered_map out performed vector in
total time, but lookup is still quicker for std::unordered_map,.
JLBorges &
Cubbi helped a lot to demonstrate and explain about that.
With the sorting algorithm, a bucket sort is very efficient. I had some thoughts about this: If there were 1 million ints, then instead of having say 1000 buckets with 1000 items in each, have 1 million buckets. There could be a relatively easy hash function to convert the int into it's bucket position, and relatively small chance of clash. To handle clashes, each bucket could contain a list with a very small number of items - 5 say. This of course is all at the expense of extra memory.