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

Question

如何快速确定unordered_map容器中是否有指定键的元素？

- Kimi

Answer 1

它们的性能大致相等。您应该使用最能表达您要做什么的算法。

详细说明一下，通常情况下，count() 将使用 find() 来实现。例如，在libcxx中，count() 实现为 return (find(__k) != end());

- Bill Lynch

Answer 2

C++20 提供了 contains 方法，结束了这一困境，该方法仍具有相同的性能，但直接表达你的意图。

- Alex Guteniev

---

contains 的源代码是否与 count 完全相同？ - Eric

@Eric，具体实现由实现者决定，一个可以调用另一个，或者两个都可以包含等效的表示。 - Alex Guteniev

Answer 3

find()和count()在C++中适用于许多容器。

对于maps、sets等容器，find()总是具有恒定的执行时间，因为它只计算哈希值，并返回找到的第一个元素的迭代器（如果没有找到则返回end()）。

另一方面，count()具有常数时间O(e)，其中e是提供的键出现的次数。最坏情况是集合中所有成员都相同，所以count()可能具有复杂度O(n)。

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

选择取决于您代码中的语义。如果您只想检查键是否存在，可以使用count。如果您想检查键是否存在并使用其值，则应选择find，因为您已经有指向该元素的迭代器。

- Visiedo

---

这是不正确的。你说find()会返回一个指针，即使实际搜索的值不存在，但它存在哈希冲突。 - A1m

更好的反驳是，“总是具有恒定的执行时间”这一说法不正确，因为它只是摊销和最优情况下的表现。在最坏情况下，查找可能是线性时间，即随着哈希冲突比例的增加趋向于线性时间。另外，如果更严谨一些的话，还可以指出这仅适用于无序映射和集合；那些不是这样标记的都是有序的，而且（通常）更慢。 - underscore_d