Standard C++ LibraryCopyright 1996, 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 part 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 container 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 conditions holds:

  !(value < *j)

  or

  comp(value, *j) == false

COMPLEXITY

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

EXAMPLE

  //
  // ul_bound.cpp
  //
   #include <vector>
   #include <algorithm>
   #include <iostream.h>

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

     // Set up a vector
    vector<int> v1(d1,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;
   }

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

WARNING

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

  vector<int, allocator<int> >

  instead of :

  vector<int>

SEE ALSO

  lower_bound, equal_range

STANDARDS CONFORMANCE

  ANSI X3J16/ISO WG21 Joint C++ Committee



privacy and legal statement