
Category: algorithms  Component type: function 
template <class ForwardIterator, class LessThanComparable> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const LessThanComparable& value); template <class ForwardIterator, class T, class StrictWeakOrdering> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);
The first version of upper_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), value < *j is false.
The second version of upper_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), comp(value, *j) is false.
int main() { int A[] = { 1, 2, 3, 3, 3, 5, 8 }; const int N = sizeof(A) / sizeof(int); for (int i = 1; i <= 10; ++i) { int* p = upper_bound(A, A + N, i); cout << "Searching for " << i << ". "; cout << "Result: index = " << p  A << ", "; if (p != A + N) cout << "A[" << p  A << "] == " << *p << endl; else cout << "which is offtheend." << endl; } }The output is:
Searching for 1. Result: index = 1, A[1] == 2 Searching for 2. Result: index = 2, A[2] == 3 Searching for 3. Result: index = 5, A[5] == 5 Searching for 4. Result: index = 5, A[5] == 5 Searching for 5. Result: index = 6, A[6] == 8 Searching for 6. Result: index = 6, A[6] == 8 Searching for 7. Result: index = 6, A[6] == 8 Searching for 8. Result: index = 7, which is offtheend. Searching for 9. Result: index = 7, which is offtheend. Searching for 10. Result: index = 7, which is offtheend.
[1] Note that you may use an ordering that is a strict weak ordering but not a total ordering; that is, there might be values x and y such that x < y, x > y, and x == y are all false. (See the LessThan Comparable requirements for a more complete discussion.) Finding value in the range [first, last), then, doesn't mean finding an element that is equal to value but rather one that is equivalent to value: one that is neither greater than nor less than value. If you're using a total ordering, however (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.
[2] Note that even if an element that is equivalent to [1] value is already present in the range [first, last), the return value of upper_bound will not point to that element. The return value is either last or else an iterator i such that value < *i. If i is not equal to first, however, then *(i  1) is less than or equivalent to value.
[3] This difference between Random Access Iterators and Forward Iterators is simply because advance is constant time for Random Access Iterators and linear time for Forward Iterators.
Contact Us  Site Map  Trademarks  Privacy  Using this site means you accept its Terms of Use 
Copyright © 2009  2017 Silicon Graphics International. All rights reserved. 