CODEWITHSUNDEEP
c++dictionarycomplexity-theorystd
Publius
Publius

Reputation: 1224

Time complexity of find() in std::map?

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?

Upvotes: 26

Views: 75062

Answers (3)

David D
David D

Reputation: 1591

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

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

Upvotes: 48

Arif Ali Saiyed
Arif Ali Saiyed

Reputation: 657

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.

Upvotes: 30

fbafelipe
fbafelipe

Reputation: 4952

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).

Upvotes: 4

Related Questions