c++ - 普通数组上的 std::lower_bound 和 std::find

Question

我喜欢在普通数组上尽可能使用 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

Answer 1

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

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

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

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

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

In terms of performance ...

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

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

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