std::find 的优点 [英] Merits of std::find

问题描述

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

Is there any advantage to using C++11's std::find over a container's find method?

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

• 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?

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

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.

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

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

推荐答案

对于 std::vector(它没有 find 方法)，std::find 是使用一些智能算法还是简单地迭代每个元素的幼稚方式?

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?

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

It cannot, because vectors are not sorted. There is no other way to find an element in an unsorted vector than a linear search with O(n) complexity.

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

On the other hand, sequence containers do not offer a find() member functions, so you could not possibly use that.

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

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)).

Indeed, here you should use the find() member function, which guarantees a better complexity (O(log N)).

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

In general, when a container exposes a member function with the same name as a generic algorithm, this is because the member function does the same thing, but offers a better complexity guarantee.

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

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

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

Just like std::vector, std::list is not a sorted container - so the same conclusion applies.

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

For std::set and std::unordered_set, instead, you should use the find() member function, which guarantees a better complexity (O(log n) and average O(1), respectively).

这篇关于std::find 的优点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！