Standard C++ LibraryCopyright 1996, Rogue Wave Software, Inc.

NAME

  lower_bound  - Determine the first valid position for an element in a
  sorted container.

SYNOPSIS

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

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

DESCRIPTION

  The lower_bound algorithm compares a supplied value to elements in a sorted
  container and returns the first position in the container that value can
  occupy without violating the container's ordering.  There are two versions
  of the algorithm.  The first uses the less than operator (operator<) to
  perform the comparison, and assumes that the sequence has been sorted using
  that operator.  The second version lets you 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.

  lower_bound's return value is the iterator for the first element in the
  container that is greater than or equal to value, or, when the comparison
  operator is used, the first element that does not satisfy the comparison
  function. Formally, the algorithm returns an iterator i in the range
  [first, last) such that for any iterator j in the range [first, i) the
  following corresponding conditions hold:

  *j  <  value

  or

  comp(*j,  value) == true

COMPLEXITY

  lower_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,2,2,2,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'll have
  to write:

  vector<int,allocator<int> >

  instead of:

  vector<int>

SEE ALSO

  upper_bound, equal_range

STANDARDS CONFORMANCE

  ANSI X3J16/ISO WG21 Joint C++ Committee



privacy and legal statement