unordered_map：find() 和 count() 哪个更快？

Question

确定

unordered_map

容器是否包含具有指定键的项目的最快方法是什么？

Answer 1

他们的表现大致相同。您应该使用最能表达您想要做的事情的算法。

详细说明一下，一般

count()

将使用

find()

来实现。例如，在 libcxx 中，

count()

实现为

return (find(__k) != end());

Answer 2

C++20 通过提供

contains

方法结束了这个困境，该方法仍然具有相同的性能，但直接说出了你的意思。

Answer 3

find()

和

count()

适用于 C++ 中的许多容器。

对于映射、集合等。

find()

将始终具有恒定的执行时间，因为它只是计算哈希值，并将迭代器返回到找到的第一个元素（如果未找到，则为

end()

）。

另一方面，

count()

具有恒定的执行时间 O(e)，其中 e 是找到所提供的密钥的次数。最坏的情况是所有成员都相同的集合，因此

count()

的复杂度可能为 O(n)

map

或

unordered_map

不允许重复，因此它们的渐近运行时间将是相同的。

选择取决于代码中的语义。如果您只想检查某个密钥是否存在，您可以使用

count

。如果您想检查某个键是否存在并使用其值，请选择

find

，因为您已经有一个指向该元素的迭代器。

Answer 4

在c++11中，“通过网站cplusplus”的时间复杂度是有区别的： unordered_map::count -> O(计数数量) 地图::计数 -> O(log) 所以你应该使用 unordered_map 来更快