CODEWITHSUNDEEP
c++performancec++11unordered-map
Kimi
Kimi

Reputation: 14099

unordered_map: which one is faster find() or count()?

What is the fastest way to figure out if an unordered_map container has an item with a specified key?

Upvotes: 47

Views: 34951

Answers (4)

Nguyễn Công Cường
Nguyễn Công Cường

Reputation: 1

"by website cplusplus" there is a difference between for time complexity:

unordered_map::count -> O (number of counted)

map::count -> O(log)

So you should use unordered_map to faster

Upvotes: -2

Alex Guteniev
Alex Guteniev

Reputation: 13689

C++20 ended the dilemma by providing contains method, which still has the same performance, but directly says what you mean.

Upvotes: 11

Visiedo
Visiedo

Reputation: 387

find() and count() are applicable to many containers in C++.

For maps, sets etc. find() will always have constant execution time, since it just calculate the hash, and returns an iterator to the first element found (end() if not found).

count() on the other hand, has a constant execution time O(e), where e is the number of times the provided key is found. The worst case is a collection where all members are the same, so count() could have a complexity O(n)

map or unordered_map do not allow for duplicates, therefore their asymptotic run time would be the same.

The choice depends on the semantics in your code. If you want just to check if a key exist, you could just use count. If you would like to check if a key exists, and use its value, then go for find since you will already have an iterator pointing to that element.

Upvotes: 6

Bill Lynch
Bill Lynch

Reputation: 81976

They will have about equal performance. You should use the algorithm that best expresses what you are trying to do.

To elaborate on that, generally count() will be implemented using find(). For example, in libcxx, count() is implemented as return (find(__k) != end());

Upvotes: 58

Related Questions