10

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

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

  • 在这种情况下,std::map您似乎需要传递 an std::pair,这是value_typean 的std::map。这似乎不是很有用,因为您通常希望找到键或映射元素。

  • 其他容器如std::listor std::setorstd::unordered_set呢?

4

1 回答 1

15

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

它不能,因为向量没有排序。除了 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::setstd::unordered_set,您应该使用find()成员函数,它可以保证更好的复杂度(分别为 O(log n) 和平均 O(1))。

于 2013-06-22T22:45:50.040 回答