lower_bound(3C++) - lower_bound(3C++)
Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.
NAMElower_bound
- Determine the first valid position for an element in a sorted con‐
tainer.
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 compari‐
son operator is used, the first element that does not satisfy the com‐
parison 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
COMPLEXITYlower_bound performs at most log(last - first) + 1 comparisons.
EXAMPLE
//
// ul_bound.cpp
//
#include <vector>
#include <algorithm>
#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,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 OutputThe 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 parameters, then you
always need to supply the Allocator template argument. For instance,
you have 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
upper_bound, equal_range
Rogue Wave Software 02 Apr 1998 lower_bound(3C++)
