110

Suppose I wanted to map data with a string as the key. What container should I have chosen, map or unordered_map? unordered_map takes up more memory so let's suppose memory isn't an issue, and the concern is speed.

unordered_map should generally give average complexity of O(1) with the worst case of O(n). In what cases would it get to O(n)? When does a map get more time efficient than unordered_map? Does it happen when n is small?

Assuming I would use STL unordered_map with the default haser Vs. map. string is the key.

If I'm going to iterate over the elements rather than access an individual element each time, should I prefer map?

Krishna Oza
  • 1,390
  • 2
  • 25
  • 50
StackHeapCollision
  • 1,743
  • 2
  • 12
  • 19
  • 3
    Do you need to items in the mapping to be sorted? – Some programmer dude Dec 10 '12 at 11:02
  • Which implementation of `unordered_map` uses more memory? – Peter Wood Dec 10 '12 at 11:07
  • You always have memory overhead in a hash map, although it is typically negligible. – ypnos Dec 10 '12 at 11:09
  • It's a minor point but as you mention iteration, it's worth pointing out that if you iterate while inserting elements, you should favor map over unordered_map. – John McFarlane Aug 29 '13 at 23:51
  • Possible duplicate of [Is there any advantage of using map over unordered\_map in case of trivial keys?](http://stackoverflow.com/questions/2196995/is-there-any-advantage-of-using-map-over-unordered-map-in-case-of-trivial-keys) – phuclv Mar 26 '17 at 16:40

5 Answers5

245
                       | map              | unordered_map
---------------------------------------------------------
element ordering       | strict weak      | n/a 
                       |                  |
common implementation  | balanced tree    | hash table
                       | or red-black tree|  
                       |                  |
search time            | log(n)           | O(1) if there are no hash collisions
                       |                  | Up to O(n) if there are hash collisions 
                       |                  | O(n) when hash is the same for any key
                       |                  |     
Insertion time         | log(n)+rebalance | Same as search
                       |                  | 
Deletion time          | log(n)+rebalance | Same as search
                       |                  | 
needs comparators      | only operator <  | only operator ==
                       |                  |
needs hash function    | no               | yes
                       |                  |
common use case        | when good hash is| In most other cases. 
                       | not possible or  | 
                       | too slow. Or when|
                       | order is required|
73

In practice, if memory is no issue, unordered_map is always faster if you want single element access.

The worst case is theoretical and bound to a single hash accounting for all of the elements. This is not of practical relevance. The unordered_map gets slower as soon as you have at least log N elements belonging to the same hash. This is also not of practical relevance. In some special scenarios you could use a specific hashing algorithm that ensures a more uniform distribution. For ordinary strings that don't share a specific pattern, the generic hash functions coming with unordered_map are just as good.

If you want to traverse the map (using iterators) in a sorted fashion, you cannot use unordered_map. On the contrary, map not only allows that, but also can provide you with the next element in a map based on an approximation of the key (see lower_bound and upper_bound methods).

ypnos
  • 50,202
  • 14
  • 95
  • 141
  • 7
    This answer is misleading at best. It's not true that "unordered_map is always faster for single element access" -- the only thing I can think of that's always true is that it's always faster *amortized* and *asymptotically*. The "amortized" is an important caveat in practce: assuming it's implemented as a hash table of some sort, if I remember my hash tables correctly, as you grow it by inserting elements, it will "hiccup" with an Ω(n) operation every so often. That may or may not be something any particular app can tolerate. – Don Hatch Oct 07 '16 at 00:22
  • Interesting term "in practice" was used. Let's say we write time-critical system, like rocket engine controller or financial trading system or cardiostimulator controller. We need a map. In 99.999% of cases std::map will be slower than std::unordered_map, well, just because average O(1) for std::unordered_map. But in 0.001% of cases we'll get worst case and O(n) for unordered_map. So what we have? Crashed rocket, lost millions, died human. Not every day, maybe even not every year. But still, worst cases happen. And std::map with worst case O(log n) can handle them, while unordered_map can't. – Ezh Mar 16 '21 at 13:17
  • 3
    If you write a rocket engine controller I hope you don't need to go and ask about basic knowledge on data structures and algorithms on Stack Overflow. This is a topic tought extensively at every university's CS bachelor program in much greater depth than the question here warrants. – ypnos Mar 16 '21 at 14:46
8

In what cases would it get to O(n)?

if you have such a bad hash function which produces the same hash value for all input stirngs (i.e. produce collisions)...

What container should I have chosen, map or unordered_map?

It is always the questions of requirements and kind/amount of data do you have.

When does a map get more time efficient than unordered_map?

It is just different structures. You'd better to make a chiose to use one of them depending on your typical use cases (takeing in account what kind of data do you have and its amount)

Does it hppaen when n is small?

In case of small data amount everything depends on particular STL implementation... So sometimes even a plain vector/array could be faster than associative containers...

zaufi
  • 6,811
  • 26
  • 34
8

What container should I have chosen, map or unordered_map? unordered_map takes up more memory so let's suppose memory isn't an issue, and the concern is speed.

Profile and then decide. unordered_map is generally faster, but it varies per case.

In what cases would it get to O(n)?

When the hashing isn't good and a bunch of elements are being assigned to the same bins.

When does a map get more time efficient than unordered_map? Does it happaen when n is small?

Probably not, but profile it if you really care. Having a container with a small size be the bottleneck of your program seems extremely unlikely. Anyway, a simple vector with linear search may be faster for such cases.

The most important thing when deciding is the requirements of ordering and lack of iterator invalidation. If you need either, you pretty much have to use map. Otherwise, unordered_map.

Pubby
  • 51,882
  • 13
  • 139
  • 180
2

std::map Internally store elements in a balanced BST. Therefore, elements will be stored in sorted order of keys.

std::unordered_map store elements using hash table. Therefore, elements will not be stored in any sorted order. They will be stored in arbitrary order .

Memory Usage :

Memory usage is more in unordered_map as compared to map because unordered_map need space for storing hash table too.

Time Complexity for Searching element :

Time complexity for searching elements in std::map is O(log n). Even in worst case it will be O(log n) because elements are stored internally as Balanced Binary Search tree (BST).

Whereas, in std::unordered_map best case time complexity for searching is O(1). Where as, if hash code function is not good then, worst case complexity can be O(n)

Shahid Hussain
  • 1,599
  • 1
  • 20
  • 24