How to choose between map and unordered map

Question

Assume I wanted to map data that had a string as the key.

Should I have used map or unordered map as my container?

Because unordered map consumes more memory, let's pretend memory isn't a problem and the only concern is performance.

The average complexity of unordered map should be O(1), with the worst case being O(2) (n).

In what circumstances would it reach O(n)?

When does a map become faster than unordered map?

Is this true when n is small?

Assuming I use STL unordered map with the default haser Vs. map, the key is string.

Should I use map if I'm going to loop through the items rather than accessing an individual element each time?

Answer 1

If memory is not a problem, unordered map is always quicker for single element access.

The worst-case scenario is theoretical and limited to a single hash that accounts for all of the components.

This has no practical application.

When there are at least log N entries belonging to the same hash, the unordered map becomes slower.

This is also irrelevant in practise.

In some cases, a specialised hashing technique that assures a more equal distribution might be used.

The generic hash functions included with unordered map are just as good for regular strings that don't share a specific pattern.

You cannot use unordered map if you wish to explore the map in a sorted manner (using iterators).

Map, on the other hand, not only supports this, but may also offer the next element in a map based on an estimate of the key (see lower bound and upper bound methods).