upper_bound(3C++) - upper_bound(3C++)
Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.
NAMEupper_bound
- Determines the last valid position for a value in a sorted con‐
tainer.
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 Com‐
pare 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 func‐
tion. Because the algorithm is restricted to using the less than opera‐
tor 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 fol‐
lowing conditions holds:
!(value < *j)
or
comp(value, *j) == false
COMPLEXITYupper_bound performs at most log(last - first) + 1 comparisons.
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 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 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
Rogue Wave Software 02 Apr 1998 upper_bound(3C++)
