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

Question

我喜欢std::algorithm在普通数组上随时使用.现在我有两个疑惑; 假设我想使用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

Answer 1

我的结果是20.(后来编辑为:打印*f时的结果为20.)

不,你得到的结果是a+6.取消调用未定义的行为.它可能打印20,它可能打印"Shirley MacLaine",或者它可能会炸毁你的车.

如果找不到,返回值是否始终是原始参数？

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

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

在表现方面......

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

在幕后std :: lower_bound调用std :: advance和std :: distance ..可能我也可以保存这些调用吗？

几乎肯定不是.在您的情况下,这些调用几乎肯定会针对单个(或极少数)指令进行优化.

Answer 2

在你的例子中,你不能取消引用f,因为它等于a+6.无论如何,你有,所以你在UB领域,但我认为值20恰好在数组之后的堆栈上a.

确实,对于足够小的数组,线性搜索可能比二进制搜索更快.10是"小",不是"大".如果你有一个程序正在对小数组进行大量搜索,你可以为每个程序计时并查看.

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

Answer 3

lower_bound和和返回的迭代器之间有一个显着的区别find.如果lower_bound找不到该项,它将返回应插入项的迭代器以保留排序顺序.如果find没有找到该项,它将返回结束迭代器(即第二个参数find).在你的例子中,因为你试图在数组的末尾找到一些东西,它们都返回相同的迭代器 - 但这完全是巧合.