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?
3 Answers
Log(n) It is based on a red black tree.
Edit: n is of course the number of members in the map.
-
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
-
2True 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
-
2@std''OrgnlDave: I think you should read this wikipedia page.
std::map::find
is definitelylog(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 believestd::map::find
has? Jul 10, 2013 at 2:41
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.
-
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. 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
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).
-
@NicolBolas: I remember reading somewhere that it wasn't mandatory a balaced tree, thanks for your comment. Fixed my anwer. Apr 1, 2012 at 6:56