24

How efficient is the find() function on the std::map class? Does it iterate through all the elements looking for the key such that it's O(n), or is it in a balanced tree, or does it use a hash function or what?

2

3 Answers 3

47

Log(n) It is based on a red black tree.

Edit: n is of course the number of members in the map.

10
  • Although this is true to an extent, there is a limitation in larger maps. If you're looking at very large datasets I'd recommend also looking at alternative associative array containers. Apr 1, 2012 at 4:16
  • 2
    True it is log(n). Not true it is based on red/black trees. The standard defines the operation to have a max complexity of log(n) and the most affective way of achieving this is to use red/black trees (though this is not a requirement). Thus you have your cart before the horse. Apr 1, 2012 at 11:33
  • 2
    @OrgnlDave: Yes it will. Standard guarantees it. I don't think you understand what complexity is (your statement may apply to absolute speed but not complexity). And 100MB is still small on modern machines, it is unlikely you could actually measure the difference. Apr 1, 2012 at 18:46
  • 1
    @OrgnlDave: NO it does not. Apr 1, 2012 at 19:51
  • 2
    @std''OrgnlDave: I think you should read this wikipedia page. std::map::find is definitely log(n). The very fact that you mention cache and "real world constraints" tells us that you have a misunderstanding of the big O notation. What complexity do you believe std::map::find has? Jul 10, 2013 at 2:41
30

std::map and std::set are implemented by compiler vendors using highly balanced binary search trees (e.g. red-black tree, AVL tree).

As correctly pointed out by David, find would take O(log n) time, where n is the number of elements in the container.

But that's with primitive data types like int, long, char, double etc., not with strings.

If std:string, lets say of size 'm', is used as key, traversing the height of the balanced binary search tree will require log n comparisons of the given key with an entry of the tree.

When std::string is the key of the std::map or std::set, find and insert operations will cost O(m log n), where m is the length of given string that needs to be found.

3
  • I was going to upvote this for pointing out that the individual comparisons are not necessarily O(1). But then you made the edit about Java, which I don't understand. The hash key returned by hashCode() is not a unique identifier, so you still need to make an O(m) string comparison when you compare two keys.
    – jogojapan
    Jul 10, 2013 at 2:36
  • Also, generating the hashcode is still O(m), so not only is it not faster, using the hashcodes would be slower (assuming they aren't cached) Jul 10, 2013 at 2:46
  • 1
    @jogojapan Thanks for pointing out java.lang.String.hashCode() thing, corrected my answer by removing the javaj portion and sticking to question being asked. Also raised a [question] ( stackoverflow.com/questions/17569651/…) Jul 10, 2013 at 11:49
4

It does not iterate all elements, it does a binary search (which is O(log(n))). It use operator< or a comparator to do the search.

If you want a hash map, you can use a std::unordered_map (added on C++-0x), which use a hash function and on average (depending on the hash function and data you provide) find() will be O(1).

1
  • @NicolBolas: I remember reading somewhere that it wasn't mandatory a balaced tree, thanks for your comment. Fixed my anwer.
    – fbafelipe
    Apr 1, 2012 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.