upper_bound

Статья
06/09/2015

Находит позицию первого элемента в упорядоченном диапазоне, который имеет значение больше указанного значения, где критерий упорядочивания может быть задан двоичным предикатом.

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

Параметры

first
Положение первого элемента в рассматриваемом диапазоне.
last
Прямой итератор, обращающийся к положению первого после элемента, после последнего в рассматриваемом диапазоне.
value
Значение в упорядоченном диапазоне, которое должно быть превышено значением элемента, адресованного возвращенным итератором.
comp
Определяемый пользователем объект функции предиката, который определяет, в каком смысле один элемент меньше другого. Двоичный предикат принимает два аргумента и возвращает true , если он удовлетворяется, и false, если не удовлетворяется.

Возвращаемое значение

Однонаправленный итератор в позиции первого элемента в упорядоченном диапазоне, который имеет значение больше или эквивалентное указанному значению.

Заметки

Сортируемый указанный диапазон источника должен быть допустимым; все итераторы должны быть dereferenceable и внутри последовательности последнего положения должна быть доступен из первого инкрементацией.

Отсортированный диапазон является предварительным условием использования upper_bound, причем критерий упорядочения такой же, как и заданный двоичным предикатом.

Этот диапазон не изменяется объектом upper_bound.

Типы значений итераторов пересылки должны быть сравнимы "меньше чем", чтобы можно было их упорядочить. Таким образом, если имеется два элемента, может быть определено, что они равны (ни один не меньше другого) или что один меньше другого. Это приводит к упорядочению неравнозначных элементов

Сложность алгоритма является логарифмической для итераторов с произвольным доступом и линейной в противном случае, с числом шагов, пропорциональным значению (last - first).

Пример

// alg_upper_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 upper_bound

    vector<int>::iterator Result;

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

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

    // upper_bound of 3 in v3 with the binary predicate  mod_lesser
    Result = upper_bound(v3.begin(), v3.end(), 3,  mod_lesser);
    cout << "The upper_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 upper_bound in v1 for the element with a value of 3 is: 4.
The upper_bound in v2 for the element with a value of 3 is: 2.
The upper_bound in v3 for the element with a value of 3 is: 4.