upper_bound

Článek
06/09/2015

Najde první element pozice zadaného rozsahu, který má hodnotu větší než zadaná hodnota, kde lze zadat kritéria řazení binárního predikátu.

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
   );

Parametry

first
Pozice prvního prvku v rozsahu, který chcete prohledat.
last
Jedna pozice za posledním prvkem v rozsahu, který chcete prohledat.
value
Hodnota v rozsahu příkazu, která musí být překročena hodnotou elementu řešenou vráceným iterátorem.
comp
Objekt funkce predikátu definovaný uživatelem, který definuje smysl, ve kterém jeden prvek je menší než jiný.Binární predikát přijímá dva argumenty a vrátí hodnotu true, když vyhovují, a hodnotu false, pokud nevyhovují.

Vrácená hodnota

Dopředná iterace na pozici prvního prvku, která má hodnotu větší než zadaná hodnota.

Poznámky

Odkazovaný seřazený zdrojový rozsah musí být platný; u všech iterátorů musí být možné zrušit referenci a poslední pozice musí být dosažitelná z první pomocí přírůstků.

Seřazený rozsah je podmínkou pro použití upper_bound a kde kritérium řazení je stejné jako u binárního predikátu.

Rozsah nebyl změněn pomocí upper_bound.

Typy hodnot iterátorů předání musí být menší než srovnatelná s hodnotou příkazu, to znamená, že když jsou uvedeny dva elementy, může být stanoveno, že jsou ekvivalentní (v tom smyslu, že ani jeden není menší než ten druhý) nebo že jeden je menší než druhý.To má za výsledek řazení mezi neekvivalentními prvky

Složitost algoritmu je logaritmický pro iterátory s náhodným přístupem a v opačném případě lineární, přičemž počet kroků je přímo úměrný (last - first).

Příklad

// 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;
}

Výsledek

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.