cpp中Lower_bound在未排序数组上的行为 [英] Behavior of lower_bound in cpp on unsorted array

问题描述

我想问一下cpp(C ++)中的lower_bound应用于未排序数组时的行为.我的意思是我运行以下程序时.

I wanted to ask how lower_bound in cpp ( C++ ) behaves when it is applied on unsorted array. I mean when I ran the following program.

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int arr[]={8,9,10,1,2,3};
    auto itr= lower_bound(arr,arr+6,7);
    cout<<*itr<<endl;
}

它给出的输出为'2'.但是根据lower_bound的定义，它将迭代器赋予失败<"的第一个元素与'val'.因此，根据此定义，答案不应该是"8"，因为"8不小于7".我知道它可以在排序数组上运行，但是我想知道这个值后面是否存在逻辑，或者它是垃圾.

it gave the output as '2'. But according to definition of lower_bound, it gives the iterator to first element which fails '<' with 'val'. So according to this definition, shouldn't the answer be '8', because "8 is not less than 7". I know it works on sorted array, but I want to know whether or not, there is a logic behind this value or is it a junk.

谢谢.

推荐答案

由于违反了提供排序数组的先决条件，因此行为未定义.您的代码两次演示了未定义的行为:首先，当您将无序数组传递给 lower_bound 时，其次，当您取消引用 iter 而未将其与 arr + 6 <进行比较时，/code>首先.

Since the precondition of supplying a sorted array has been violated, the behavior is undefined. Your code demonstrates undefined behavior twice: first, when you pass an unordered array to lower_bound, and second, when you dereference iter without comparing it to arr+6 first.

很容易看到发生了什么: lower_bound 背后的算法是基本的二进制搜索.您为算法提供一个数组，它将它们分为两半，并检查中间的项.您提供了偶数个项目，有两个数字可以被认为是在中间"-10和1.看起来算法选择了 1 并将其与搜索项目7进行了比较然后继续在数组的上半部分搜索，检查2和3，最后返回指向数组末尾的指针.

It is easy to see what is going on, though: the algorithm behind lower_bound is a basic binary search. You give the algorithm an array, it divides them in two halves, and checks the item in the middle. You supplied an even number of items, there are two numbers that can be considered "being in the middle" - 10 and 1. It looks like the algorithm picked 1, compared it to your search item 7, and continued search in the upper half of the array, checks 2 and 3, and finally returns the pointer pointing past the end of the array.

当取消引用该指针时，您将得到垃圾；不幸的是，它恰好与您的数组元素之一匹配，即2，导致您得出错误的结论.

When you dereference that pointer, you get junk; unfortunately, it happens to match one of the elements of your array, i.e. 2, leading you to a wrong conclusion.

按如下所示更改代码，以查看实际返回的内容:

Change your code as follows to see what is actually returned:

int arr[]={8,9,10,1,2,3, -1};

现在在索引6处取消对元素的引用是有效的；您的代码可能应该显示 -1 (尽管这是针对特定系统的未定义行为的利用，并且不能保证在其他系统上产生相同的结果).

Now dereferencing the element at index 6 is valid; your code should probably print -1 (although this is an exploit of undefined behavior specific to your particular system, and it is not guaranteed to produce the same results on other systems).

这篇关于cpp中Lower_bound在未排序数组上的行为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！