C++ std::lower_bound 和 std::find 在普通数组上

std::lower_bound and std::find on a plain array

提问by Abruzzo Forte e Gentile

I like to use std::algorithmwhenever I can on plain arrays. Now I have 2 doubts; suppose I want to use std::lower_boundwhat happens if the value I provide as argument is not found?

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

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

The result I have when printing *f is 20.

打印 *f 时的结果是 20。

The same happens if I use std::find.

如果我使用std::find.

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

The result I have when printing *f is 20.

打印 *f 时的结果是 20。

1. Is it always the case that the return value is the original argument when this is not found?
2. In terms of performance std::lower_boundperforms better of std::findsince it implements a binary search algorithm. If the array is big say max 10 elements, could std::find perform better? Behind the scenes std::lower_bound calls std::advance and std::distance ..maybe I might save on these calls as well?

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

Thanks a lot

非常感谢

AFG

AFG

回答by Rob?

The result I have is 20. (Later edited to: The result I have when printing *f is 20.)

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

No, the result you get is a+6. Dereferncing that invokes undefined behavior. It might print 20, it might print "Shirley MacLaine", or it might blow up your car.

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

Is it always the case that the return value is the original argument when this is not found?

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

The return value will always be the 2ndargument in your case, because 20 is larger than any other value in the array. If the value is not found, but smaller than some existing value, the return value points to the next larger item.

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

From cppreference.com, the return value of std::lower_bound is "iterator pointing to the first element that is not less than value, or lastif no such element is found."

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

In terms of performance ...

在性能方面...

Measure it. No other advice here will stand up to your actual empirical evidence.

测量它。这里没有其他建议经得起你的实际经验证据。

Behind the scenes std::lower_bound calls std::advance and std::distance ..maybe I might save on these calls as well?

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

Almost certainly not. Those calls are almost certainly optimized in your case to single (or very few) instructions.

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

回答by Mark Ransom

There's one significant difference between the iterators returned by lower_boundand find. If lower_bounddoesn't find the item, it will return the iterator where the item should be inserted to retain the sort order. If finddoesn't find the item, it will return the ending iterator (i.e. the second argument to find). In your example since you're trying to find something off the end of the array, both return the same iterator - but that's a complete coincidence.

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

回答by Steve Jessop

In your example you must not dereference f, because it's equal to a+6. You have anyway, so you're in UB territory, but I suppose that the value 20 happens to be on the stack immediately after the array a.

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

It's true that for small enough arrays, a linear search might be faster than a binary search. 10 is "small", not "big". If you have a program which is doing a lot of searches into small arrays, you can time each one and see.

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

There should be basically no overhead for std::advanceand std::distance- any halfway competent C++ compiler will inline everything, and they'll turn into pointer addition and subtraction.

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

回答by Ankit Kumar

You could use the following implementation

您可以使用以下实现

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

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

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

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

Now if 20 is present in the array it will return the index of the element in the array a (0-based indexing used). If 20 is not present in the array it will return 6 i.e. the length of the array.

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

In worst case the item to be searched is present at (n-1)th index [when n is the size of the array]. Then f will be n-1.

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

f will be n or equal to the size of the array only when the item being searched is not present in the array.

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

Hope it answers your question.

希望它能回答你的问题。