
Category: algorithms  Component type: function 
template <class ForwardIterator, class LessThanComparable> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const LessThanComparable& value); template <class ForwardIterator, class T, class StrictWeakOrdering> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);
The first version of lower_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), *j < value.
The second version of lower_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), comp(*j, value) is true.
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 = lower_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 = 0, A[0] == 1 Searching for 2. Result: index = 1, A[1] == 2 Searching for 3. Result: index = 2, A[2] == 3 Searching for 4. Result: index = 5, A[5] == 5 Searching for 5. Result: index = 5, A[5] == 5 Searching for 6. Result: index = 6, A[6] == 8 Searching for 7. Result: index = 6, A[6] == 8 Searching for 8. Result: index = 6, A[6] == 8 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] If an element that is equivalent to [1] value is already present in the range [first, last), then the return value of lower_bound will be an iterator that points to that element.
[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. 