Return the last position in the range [ first ... last ) in which value can be inserted without violating the order of the collection. The first version uses operator< for comparison, whereas the second version uses the binary function compare .

Declaration


  
#include <algorithm>

template< class ForwardIterator, class T >
ForwardIterator upper_bound
  (
  ForwardIterator first,
  ForwardIterator last,
  const T& value
  );

template< class ForwardIterator, class T, class Compare >
ForwardIterator upper_bound
  (
  ForwardIterator first,
  ForwardIterator last,
  const T& value,
  Compare compare
  );

Complexity

Time complexity is O(log(N)) for random access iterators, O(N) for all other iterators. Space complexity is constant.

Example <ospace/osstd/examples/uprbnd1.cpp>


    #include <iostream>
#include <algorithm>

int main()
  {
  int array[ 20 ];
  for ( int i = 0; i < 20; ++i )
    {
    array[ i ] = i/4;
    cout << array[ i ] << ` `;
    }
  cout
    << "\n3 can be inserted at index: "
    << upper_bound( array, array + 20, 3 ) - array
    << "\n";
  }

0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
3 can be inserted at index: 16

Example <ospace/osstd/examples/uprbnd2.cpp>


    #include <iostream>
#include <string.h>
#include <algorithm>

char* str[] = { "a", "a", "b", "b", "q", "w", "z" };

bool char_str_less( const char* a_, const char* b_ )
  {
  return ::strcmp( a_, b_ ) < 0 ? 1 : 0;
  }

int main()
  {
  const unsigned str_ct = sizeof( str )/sizeof( str[ 0 ] );
  cout
    << "d can be inserted at index: "
    << upper_bound( str, str + str_ct, "d", char_str_less ) - str
    << "\n";
  }

d can be inserted at index: 4

upper_bound

Library

Declaration

Complexity

Example <ospace/osstd/examples/uprbnd1.cpp>

Example <ospace/osstd/examples/uprbnd2.cpp>