How do you tell if an entry with a specific key has been inserted in a std::map and std::unordered_map? Historically the way was to call find and compare against end, e.g.

if(m.find(x) != m.end()) // If present:
	// do something

With the introduction of C++11, there is another technique - calling count.

if(m.count(x) != 0) // If present:
	// do something

Count returns the number of entries with the given key.

Note also that in std::map and std::unordered_map, count can only return 0 (in the case where the entry is not present) and 1 (when it is). Multiple entries with the same key are not allowed in a map or unordered_map.

You might think that both techniques for testing if an element with a given key is in a map would have similar performance, but this is not the case with some implementations.

Performance result for VS2015, Release build:

std::map count:           1.196503 s, keys_present: 10000000
std::map find:            0.612619 s, keys_present: 10000000
std::unordered_map count: 0.232709 s, keys_present: 10000000
std::unordered_map find:  0.134992 s, keys_present: 10000000

What we see is that count takes about twice the time that find does.

Why does count take so long? Stepping through the code in the VS debugger reveals the answer. Count calls equal_range, which computes the range of elements with the same key. equal_range effectively does two tree traversals, one for the start of the range, and one for the end. This is the reason why count takes approximately twice as long (at least for std::map).

I haven't looked into why std::unordered_map::count is slow but I assume it's for a similar reason.

Proposed solution

My proposed solution is to replace the implementation of std::map::count with something like the following:

size_t count(Keyval& k)
{
	return (find(k) == end()) ? 0 : 1;
}

Based on the test results above, this should make count approximately two times faster for std::map.

More results

Clang (clang version 3.6.0 (trunk 225608)) on Linux:

std::map count:           0.715613 s, keys_present: 10000000
std::map find:            0.708204 s, keys_present: 10000000
std::unordered_map count: 0.200249 s, keys_present: 10000000
std::unordered_map find:  0.110208 s, keys_present: 10000000

Only std::unordered_map::count seems to suffer from this problem, std::map::count is fine.

Xcode (Apple LLVM version 7.3.0 (clang-703.0.31)):

std::map count:           0.392112 s, keys_present: 10000000
std::map find:            0.413565 s, keys_present: 10000000
std::unordered_map count: 0.142392 s, keys_present: 10000000
std::unordered_map find:  0.159157 s, keys_present: 10000000

This std lib does not seem to have the problem.

Test source code: map_count_slowness.cpp.

Edit: discussion on reddit here.