std :: find的优点 [英] Merits of std::find
问题描述
在容器的 find
方法中使用C ++ 11的 std :: find
有什么好处? / p>
-
在
std :: vector
的情况下(没有一个find
方法) std :: find 使用一些智能算法或简单迭代每个元素的简单方法?
-
在
std :: map 的情况下,似乎需要传递 std :: pair
,它是std :: map
value_type >。这看起来不是很有用,因为通常你想找到一个键或映射元素。 -
其他容器,如
std :: list
或std :: set
或std :: unordered_set
?
解决方案
在std的情况下: :vector(没有find方法)std :: find是否使用了一些智能算法或简单迭代每个元素的简单方法?
它不能,因为向量没有排序。除了O(n)复杂度的线性搜索之外,没有其他方法可以找到未分类向量中的元素。另一方面,序列容器不提供
find()
成员函数,所以你不可能使用。
在std :: map的情况下,你需要传递一个std :: pair,它是value_type一个std :: map。这看起来不是很有用,因为通常你想要找到一个键或映射元素。
的确,在这里你应该使用
find()
成员函数,这保证了更好的复杂性(O(log N))。一般来说,当一个容器公开一个与通用算法同名的成员函数时,这是因为成员函数做同样的事情,但提供了一个更好的复杂性保证。 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?In the case of
std::map
it seems you need to pass along anstd::pair
, which is thevalue_type
of anstd::map
. This does not seem very useful as usually you'd want to find for either a key or a mapped element.What about other containers like
std::list
orstd::set
orstd::unordered_set
?
其他容器如std :: list或std :: set或std :: unordered_set?
$ b $
就像 std :: vector
, std :: list
不是一个已排序的容器 - 所以结论同样适用。
对于 std :: set
和 std :: unordered_set
,而应该使用 find()
成员函数,这样可以保证更好的复杂性(O n)和平均O(1),分别)。
Is there any advantage to using C++11's std::find
over a container's find
method?
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?
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.
On the other hand, sequence containers do not offer a find()
member functions, so you could not possibly use that.
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.
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.
What about other containers like std::list or std::set or std::unordered_set ?
Just like std::vector
, std::list
is not a sorted container - so the same conclusion applies.
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屋!