Man Page upper_bound.3

                       Standard C++ Library
             Copyright 1998, Rogue Wave Software, Inc.

NAME

     upper_bound

      - Determines the last valid  position  for  a  value  in  a
     sorted container.

SYNOPSIS

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

DESCRIPTION

     The upper_bound algorithm is one of a set of  binary  search
     algorithms.  All of these algorithms perform binary searches
     on ordered containers. Each algorithm has two versions.  The
     first  version  uses  the  less than operator (operator<) to
     perform the comparison, and assumes that  the  sequence  has
     been  sorted  using that operator. The second version allows
     you to include  a  function  object  of  type  Compare,  and
     assumes  that  Compare  is  the  function  used  to sort the
     sequence. The function object must be a binary predicate.

     The upper_bound algorithm finds the last position in a  con-
     tainer   that   value   can  occupy  without  violating  the
     container's ordering.  upper_bound's  return  value  is  the
     iterator  for  the  first  element  in the container that is
     greater than value, or,  when  the  comparison  operator  is
     used, the first element that does NOT satisfy the comparison
     function. Because the algorithm is restricted to  using  the
     less  than  operator or the user-defined function to perform
     the search, upper_bound returns an iterator i in  the  range
     [first,  last)  such  that  for  any iterator j in the range
     [first, i) the appropriate version of the  following  condi-
     tions holds:

     !(value < *j)
     or

     comp(value, *j) == false

COMPLEXITY

     upper_bound performs at most log(last - first) + 1 comparis-
     ons.

EXAMPLE

     //
     // ul_bound.cpp
     //
     #include <vector>
     #include <algorithm>
     #include <functional>
     #include <iostream>
     using namespace std;

     int main()
      {
     typedef vector<int>::iterator iterator;
     int d1[11] = {0,1,2,2,3,4,2,2,2,6,7};

     // Set up a vector
     vector<int> v1(d1 + 0,d1 + 11);

     // Try lower_bound variants
     iterator it1 = lower_bound(v1.begin(),v1.end(),3);
     // it1 = v1.begin() + 4

     iterator it2 =
       lower_bound(v1.begin(),v1.end(),2,less<int>());
     // it2 = v1.begin() + 4

     // Try upper_bound variants
     iterator it3 = upper_bound(v1.begin(),v1.end(),3);
     // it3 = vector + 5

     iterator it4 =
        upper_bound(v1.begin(),v1.end(),2,less<int>());
     // it4 = v1.begin() + 5
     cout << endl << endl
          << "The upper and lower bounds of 3: ( "
          << *it1 << " , " << *it3 << " ]" << endl;
     cout << endl << endl
          << "The upper and lower bounds of 2: ( "
          << *it2 << " , " << *it4 << " ]" << endl;
     return 0;
      }

     Program Output




     The upper and lower bounds of 3: ( 3 , 4 ]
     The upper and lower bounds of 2: ( 2 , 3 ]

WARNINGS

     If your compiler does not support default  template  parame-
     ters,  then you always need to supply the Allocator template
     argument. For instance, you need to write:

     vector<int, allocator<int> >

     instead of:

     vector<int>

     If your compiler does not support namespaces,  then  you  do
     not need the using declaration for std.

SEE ALSO

     lower_bound, equal_range