问题描述
与容器的 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 afind
method) doesstd::find
use some smart algorithm or the naive way of simply iterating over every element?
在 std::map
的情况下,您似乎需要传递一个 std::pair
,即 value_type
std::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 的优点的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!