44

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?

ildjarn
  • 62,044
  • 9
  • 127
  • 211
stewart99
  • 14,024
  • 7
  • 27
  • 42

3 Answers3

63

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.

Andy Prowl
  • 124,023
  • 23
  • 387
  • 451
  • `unordered_map` is still going to vary based on the size of the strings, isn't it? Each lookup will require a hash generation and a key comparison for each item in the bucket. – Mark Ransom Apr 17 '13 at 19:12
  • 5
    @MarkRansom: Complexity is normally measured in terms of the size of the container, i.e. the number of elements it contains. The length of the strings could surely have an impact on performance, but it does not affect computational complexity – Andy Prowl Apr 17 '13 at 19:14
  • Yes I know that `O` notation doesn't express this at all, but it does seem to be a concern in the question. – Mark Ransom Apr 17 '13 at 19:18
  • @MarkRansom: I may be wrong, but it seems to me the OP is concerned with computational complexity here – Andy Prowl Apr 17 '13 at 19:22
  • I agree with Mark in that the question of whether `O(1)` can be obtained with a string key might hint that the user is interested in this. – David Rodríguez - dribeas Apr 17 '13 at 19:26
  • @DavidRodríguez-dribeas: OK, then I trust you guys. I have expanded my answer a bit. – Andy Prowl Apr 17 '13 at 19:37
  • @MarkRansom: It seems you may be right about the OP's concerns. I expanded my answer – Andy Prowl Apr 17 '13 at 19:38
  • 1
    Thanks for the update. I would +1 but you already got it long ago, since everything you said was absolutely true. – Mark Ransom Apr 17 '13 at 19:52
  • @MarkRansom -- You are correct reg. "*Each lookup will require a hash generation*" but wrong reg. "*[Each lookup will require] a key comparison for* **each** *item in the bucket*". If the latter were correct, then the complexity becomes linear. All O(1) says is that it is *independent* of the number of items in the container. For all one knows, it could take eternity to compute the hash itself. – Happy Green Kid Naps May 03 '13 at 22:46
  • @HappyGreenKidNaps, yes a hash table can become linear if all the hashes wind up in the same bucket. That usually doesn't happen though. Notice the quote in the answer: "worst case O(size())". It has been known for a service to be attacked by specifically choosing keys that have the same hash, if the hash algorithm is known. See e.g. http://www.anchor.com.au/blog/2012/12/how-to-explain-hash-dos-to-your-parents-by-using-cats/ – Mark Ransom May 04 '13 at 00:35
  • @MarkRansom -- big difference between "will" and "can" (as you have noted yourself -- it makes the difference between "worst case" and "average case"). – Happy Green Kid Naps May 06 '13 at 19:28
6

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.

Shafik Yaghmour
  • 154,301
  • 39
  • 440
  • 740
  • 3
    *Expected* `O(1)`. It is fairly easy to build a degenerate case where it is `O(N)`. –  Apr 17 '13 at 19:09
3

Basicaly std::map is implimented using red-black tree. In red-black tree insert ans delete operation take O(LogN) time, so in std::map time complexity is O(LogN) of every element.

std::unodered_map is implememted using hashing ,where every operation take O(1) time.

Savaliya Vivek
  • 49
  • 4