How to choose between map and unordered_map?

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?

                       | 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| 

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).

> 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.

> 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...

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)