17

我喜欢std::algorithm尽可能在普通数组上使用。现在我有2个疑问；假设我想使用std::lower_bound如果我作为参数提供的值没有找到会发生什么？

int a[] = {1,2,3,4,5,6};
int* f = std::lower_bound(a,a+6,20);

打印 *f 时的结果是 20。

如果我使用std::find.

int a[] = {1,2,3,4,5,6};
int* f = std::find(a,a+6,20);

打印 *f 时的结果是 20。

  1. 当找不到返回值时，是否总是返回值是原始参数？
  2. 在性能方面表现std::lower_bound更好，std::find因为它实现了二进制搜索算法。如果数组很大，比如最多 10 个元素，std::find 性能会更好吗？在幕后 std::lower_bound 调用 std::advance 和 std::distance ..也许我也可以节省这些调用？

非常感谢

AFG

4

4 回答 4

19

我得到的结果是 20。（后来编辑为：打印 *f 时得到的结果是 20。）

不，你得到的结果是a+6. 取消引用调用未定义的行为。它可能会打印 20，可能会打印“Shirley MacLaine”，或者可能会炸毁您的汽车。

当找不到返回值时，是否总是返回值是原始参数？

在您的情况下，返回值将始终是第二个参数，因为 20 大于数组中的任何其他值。如果未找到该值，但小于某个现有值，则返回值指向下一个较大的项。

从cppreference.com， std::lower_bound 的返回值是“指向不小于 的第一个元素的迭代器value，或者last如果没有找到这样的元素。”

在性能方面...

测量它。这里没有其他建议可以与您的实际经验证据相提并论。

在幕后 std::lower_bound 调用 std::advance 和 std::distance ..也许我也可以节省这些调用？

几乎可以肯定不是。在您的情况下，这些调用几乎肯定会针对单个（或很少）指令进行优化。

于 2012-06-01T15:56:20.390 回答
7

lower_bound和返回的迭代器之间有一个显着差异find。如果lower_bound没有找到该项目，它将返回应该插入该项目以保留排序顺序的迭代器。如果find没有找到该项目，它将返回结束迭代器（即第二个参数find）。在您的示例中，因为您试图在数组末尾找到一些东西，所以两者都返回相同的迭代器 - 但这完全是巧合。

于 2012-06-01T16:07:24.923 回答
6

在您的示例中，您不能取消引用f，因为它等于a+6. 无论如何，你有，所以你在 UB 领域，但我想值 20 恰好在 array 之后立即在堆栈上a。

确实，对于足够小的数组，线性搜索可能比二分搜索更快。10 是“小”，不是“大”。如果您有一个程序对小数组进行大量搜索，您可以对每个数组进行计时并查看。

基本上应该没有开销std::advance和std::distance- 任何能胜任的 C++ 编译器都会内联所有内容，它们将变成指针加法和减法。

于 2012-06-01T15:57:50.707 回答
4

您可以使用以下实现

int a[] = {1,2,3,4,5,6};

int f = lower_bound(a,a+6,20)-a;

现在，如果数组中存在 20，它将返回数组 a 中元素的索引（使用基于 0 的索引）。如果数组中不存在 20，它将返回 6，即数组的长度。

在最坏的情况下，要搜索的项目出现在第 (n-1) 个索引处[当 n 是数组的大小时]。那么 f 将是 n-1。

仅当正在搜索的项目不存在于数组中时， f 才会为 n 或等于数组的大小。

希望它能回答你的问题。

于 2018-06-04T04:59:33.563 回答