unordered_map:哪一个更快找到()或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因为您已经有一个指向该元素的迭代器。