lower_bound

아티클
06/09/2015

지정된 값보다 크거나 같은 값을 갖는 정렬된 범위에 있는 첫 번째 요소의 위치를 찾습니다. 정렬 기준은 이진 조건자로 지정할 수 있습니다.

template<class ForwardIterator, class Type> 
   ForwardIterator lower_bound( 
      ForwardIterator first,  
      ForwardIterator last, 
      const Type& value 
   ); 
template<class ForwardIterator, class Type, class BinaryPredicate> 
   ForwardIterator lower_bound( 
      ForwardIterator first,  
      ForwardIterator last, 
      const Type& value,
      BinaryPredicate comp 
   );

매개 변수

first
검색할 범위에 있는 첫 번째 요소의 위치를 가리키는 정방향 반복기입니다.
last
검색할 범위에 있는 마지막 요소의 하나 뒤 위치를 가리키는 정방향 반복기입니다.
value
첫 번째 위치 또는 가능한 첫 번째 위치가 순서가 지정된 범위에서 검색되는 값입니다.
comp
한 요소가 다른 요소보다 작은 개념을 정의하는 사용자 정의 조건자 함수 개체입니다. 이진 조건자는 두 개의 인수를 사용하고 만족할 때는 true를 만족하지 못할 때는 false를 반환합니다.

반환 값

지정된 값보다 크거나 같은 값으로 정렬된 범위에 있는 첫 번째 요소의 위치에 있는 정방향 반복기입니다. 같은지 여부는 이진 조건자로 지정됩니다.

설명

참조된 정렬된 소스 범위는 유효해야 하며 모든 반복기는 역참조할 수 있어야 하고 시퀀스 내에서 마지막 위치는 처음부터 증분 만큼 접근할 수 있어야 합니다.

정렬된 범위는 lower_bound 사용을 위한 사전 조건이며, 순서 지정은 이진 조건자에서 지정한 것과 같습니다.

범위는 lower_bound 알고리즘에 의해 수정되지 않습니다.

정방향 반복기의 값 형식은 순서가 지정될 비교 가능한 값보다 작아야 합니다. 제공된 두 개 요소에서 두 요소가 동일하거나(어떤 것도 다른 것보다 작지 않음) 하나가 다른 것보다 작음을 정할 수 있습니다. 그러면 동일하지 않은 요소 사이에 정렬이 수행됩니다.

알고리즘의 복잡성은 임의 액세스 반복기 및 선형에 대한 로그이며 반대의 경우는 비례하는 단계의 수(last – first)입니다.

예제

// alg_lower_bound.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>      // greater<int>( )
#include <iostream>

// Return whether modulus of elem1 is less than modulus of elem2
bool mod_lesser( int elem1, int elem2 )
{
    if ( elem1 < 0 )
        elem1 = - elem1;
    if ( elem2 < 0 )
        elem2 = - elem2;
    return elem1 < elem2;
}

int main( )
{
    using namespace std;

    vector<int> v1;
    // Constructing vector v1 with default less-than ordering
    for ( auto i = -1 ; i <= 4 ; ++i )
    {
        v1.push_back(  i );
    }

    for ( auto ii =-3 ; ii <= 0 ; ++ii )
    {
        v1.push_back(  ii  );
    }

    cout << "Starting vector v1 = ( " ;
    for (const auto &Iter : v1)
        cout << Iter << " ";
    cout << ")." << endl;

    sort(v1.begin(), v1.end());
    cout << "Original vector v1 with range sorted by the\n "
        << "binary predicate less than is v1 = ( " ;
    for (const auto &Iter : v1)
        cout << Iter << " ";
    cout << ")." << endl;

    // Constructing vector v2 with range sorted by greater
    vector<int> v2(v1);

    sort(v2.begin(), v2.end(), greater<int>());

    cout << "Original vector v2 with range sorted by the\n "
        << "binary predicate greater is v2 = ( " ;
    for (const auto &Iter : v2)
        cout << Iter << " ";
    cout << ")." << endl;

    // Constructing vectors v3 with range sorted by mod_lesser
    vector<int> v3(v1);
    sort(v3.begin(), v3.end(), mod_lesser);

    cout << "Original vector v3 with range sorted by the\n "
        <<  "binary predicate mod_lesser is v3 = ( " ;
    for (const auto &Iter : v3)
        cout << Iter << " ";
    cout << ")." << endl;

    // Demonstrate lower_bound

    vector<int>::iterator Result;

    // lower_bound of 3 in v1 with default binary predicate less<int>()
    Result = lower_bound(v1.begin(), v1.end(), 3);
    cout << "The lower_bound in v1 for the element with a value of 3 is: "
        << *Result << "." << endl;

    // lower_bound of 3 in v2 with the binary predicate greater<int>( )
    Result = lower_bound(v2.begin(), v2.end(), 3, greater<int>());
    cout << "The lower_bound in v2 for the element with a value of 3 is: "
        << *Result << "." << endl;

    // lower_bound of 3 in v3 with the binary predicate  mod_lesser
    Result = lower_bound(v3.begin(), v3.end(), 3,  mod_lesser);
    cout << "The lower_bound in v3 for the element with a value of 3 is: "
        << *Result << "." << endl;
}

Output

Starting vector v1 = ( -1 0 1 2 3 4 -3 -2 -1 0 ).
Original vector v1 with range sorted by the
 binary predicate less than is v1 = ( -3 -2 -1 -1 0 0 1 2 3 4 ).
Original vector v2 with range sorted by the
 binary predicate greater is v2 = ( 4 3 2 1 0 0 -1 -1 -2 -3 ).
Original vector v3 with range sorted by the
 binary predicate mod_lesser is v3 = ( 0 0 -1 -1 1 -2 2 -3 3 4 ).
The lower_bound in v1 for the element with a value of 3 is: 3.
The lower_bound in v2 for the element with a value of 3 is: 3.
The lower_bound in v3 for the element with a value of 3 is: -3.