Standard C++ Library Class Reference

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)

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,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