정렬되지 않은 배열의 cpp에서 lower_bound의 동작

Question

cpp (C++)의 lower_bound가 정렬되지 않은 배열에 적용될 때 어떻게 동작하는지 질문하고 싶습니다. 다음 프로그램을 실행했을 때를 의미합니다.

#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은 7보다 작지 않으므로"8이되어야합니다. 정렬 된 배열에서 작동한다는 것을 알고 있지만,이 값 뒤에 로직이 있는지 또는 정크인지 여부를 알고 싶습니다.

감사합니다.

Answer 1

정렬 된 배열을 제공하기위한 전제 조건이 위반되었으므로 동작이 정의되지 않습니다. 코드는 정의되지 않은 동작을 두 번 나타냅니다. 첫째, 순서가 지정되지 않은 배열을 lower_bound에 전달하면 iter을 참조하지 않고 arr+6과 우선 비교합니다.

어떤 일이 일어나는지 쉽게 알 수 있습니다. lower_bound 뒤에있는 알고리즘은 기본 이진 검색입니다. 알고리즘에 배열을 두 개로 나누고 중간에있는 항목을 검사합니다. 당신은 짝수 개의 항목을 제공했습니다. "중간에있는"것으로 간주 될 수있는 두 개의 숫자 - 10과 1이 있습니다. 알고리즘을 선택 한 결과 1이 검색 항목 7과 비교되어 상반부에서 계속 검색됩니다 배열의 2와 3을 검사하고, 마지막으로 은 배열을지나 가리키는 포인터를 반환합니다.

포인터를 역 참조하면 정크가됩니다. 안타깝게도 배열의 요소 중 하나 (예 : 2)와 일치하여 잘못된 결론을 유도합니다. 실제로 반환 상황을 확인하기 위해 다음과 같이

이 코드를 변경

:

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

이제 6이 유효 인덱스에있는 요소를 역 참조; 코드는 아마 -1을 인쇄해야합니다 (이것은 특정 시스템에 특정한 정의되지 않은 동작을 악용하는 것이지만 다른 시스템에서 동일한 결과를 생성하는 것은 아닙니다).