Skip to content. Skip to navigation

ICTP Portal

Sections
You are here: Home Manuals on-line PGI Compiler pgC_lib upper_bound
Personal tools
Document Actions

upper_bound



Click on the banner to return to the class reference home page.

upper_bound


Algorithm

Summary

Determines the last valid position for a value in a sorted container.

Data Type and Member Function Indexes
(exclusive of constructors and destructors)

None

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,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 will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

See Also

lower_bound, equal_range


©Copyright 1996, Rogue Wave Software, Inc.


Powered by Plone This site conforms to the following standards: