c++ - std::find 的优点

Question

与容器的 find 方法相比，使用 C++11 的 std::find 有什么优势吗？

• 在 std::vector 的情况下(没有 find 方法)std::find 使用一些智能算法或简单地迭代每个元素的天真方法？

• 在 std::map 的情况下，您似乎需要传递一个 std::pair，即 value_typestd::map 的。这似乎不是很有用，因为通常您希望查找键或映射元素。

• std::list 或 std::set 或 std::unordered_set 等其他容器呢？

Answer 1

In the case of std::vector (which does not have a find method) does std::find use some smart algorithm or the naive way of simply iterating over every element?

它不能，因为 vector 没有排序。除了具有 O(n) 复杂度的线性搜索之外，没有其他方法可以在未排序的 vector 中找到元素。

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

In the case of std::map it seems you need to pass along an std::pair, which is the value_type of an std::map. This does not seem very useful as usually you'd want to find for either a key or a mapped element.

的确，这里您应该使用find() 成员函数，它保证了更好的复杂度(O(log N))。

一般来说，当一个容器暴露一个与泛型算法同名的成员函数时，这是因为该成员函数做同样的事情，但提供了更好的复杂性保证。

What about other containers like std::list or std::set or std::unordered_set ?

就像 std::vector 一样，std::list 不是排序的容器 - 所以同样的结论适用。

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