std::find的优点

Question

std::find的优点

9

是否使用C++11的std::find函数比容器自带的find方法要更加优越？

- 在std::vector这种没有find方法的情况下，std::find是使用智能算法还是朴素方式遍历每个元素呢？ - 在std::map这种情况下，似乎需要传递一个std::pair作为参数，这是std::map的value_type。这看起来并不是很实用，因为通常你想查找的是键或映射元素。 - 对于其他容器，如std::list、std::set或std::unordered_set等呢？

- rwols

1

你可以在std::map上使用std::find_if来仅比较键。但是在这种情况下最好使用find成员函数，因为它更高效。然而，如果出于某种原因你想按值搜索映射，那么你可以在这种情况下使用find_if。 - Benjamin Lindley

3

如果存在成员函数，使用该成员函数；否则使用std::find。 - Mooing Duck

如果您知道您的std::vector实际上是已排序的，那么始终可以使用std::lower_bound()来进行二分查找。 - Adam

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andy Prowl · Accepted Answer

在 std::vector （没有 find 方法）的情况下，std::find 使用一些智能算法还是简单迭代每个元素的 naive 方法？答：不能使用智能算法因为向量没有排序。在无序向量中查找元素没有其他方法，只能使用一种时间复杂度为O(n)的线性搜索。

另一方面，序列容器不提供 find() 成员函数，所以你不可能使用它。

在 std::map 的情况下，似乎需要传递一个 std::pair，这是 std::map 的 value_type。这似乎并不太有用，因为通常您要查找键或映射元素。答：确实，这里应该使用 find() 成员函数，它保证了更好的时间复杂度（O(log N)）。

总的来说，当一个容器暴露出与通用算法同名的成员函数时，这是因为成员函数做相同的事情，但提供了更好的时间复杂度保证。

其他容器如 std::list、std::set 或 std::unordered_set 呢？答：就像 std::vector 一样，std::list 不是一个已排序的容器 - 因此相同的结论适用。

对于 std::set 和 std::unordered_set，您应该使用 find() 成员函数，它们保证更好的时间复杂度（分别是 O(log n) 和平均 O(1)）。