C++ STL map: is access time O(1)?

Question

Is key look up on std::map O(1)? I thought it was until I thought about it more. It is based on a tree implementation so the lookup time should be O(log N), correct?

And, is it possible to have O(1) look up on string key, std::unordered_map perhaps?

Answer 1

The complexity of lookup for std::map is O(log N) (logarithmic in the size of the container).

Per Paragraph 23.4.4.3/4 of the C++11 Standard on std::map::operator []:

Complexity: logarithmic.

The complexity of lookup for std::unordered_map is O(1) (constant) in the average case, and O(N) (linear) in the worst case.

Per Paragraph 23.5.4.3/4 of the C++11 Standard on std::unordered_map::operator []

Complexity: Average case O(1), worst case O(size()).

NOTE:

If your question is only concerned with computational complexity, then what written above should answer it. The computational complexity of an operation, in fact, is measured in terms of the size of the container (the number of elements it contains).

However, if you are looking for a way to perform O(1) lookup on a container that uses string keys, and where the complexity of the lookup is constant with respect to the length of the string rather than to the size of the container, then the answer is that std::unordered_map won't meet your requirements.

In order to lookup a key, it is first necessary to produce a hash of it; when the key is a string, this operation itself could be linear in the size of the string. Then, the implementation has to compare the key to all the string keys in the same bucket, and each of these comparisons is in turn linear in the size of those strings.

Answer 2

Yes, indeed std::map will be O(log N) and std::unordered_map will have average constant-time complexity and O(N) in the worst case if there are too many hash collisions.