Книга: Standard Template Library Programmer
upper_bound
Разделы на этой странице:
upper_bound
Category: algorithms
Component type: function
Prototype
Upper_bound is an overloaded name; there are actually two upper_bound functions.
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);
Description
Upper_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last) [1]. Specifically, it returns the last position where value could be inserted without violating the ordering. [2] The first version of upper_bound uses operator< for comparison, and the second uses the function object 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.
Definition
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
Requirements on types
For the first version:
• ForwardIterator is a model of Forward Iterator.
• LessThanComparable is a model of LessThan Comparable.
• The ordering on objects of type LessThanComparable is a strict weak ordering, as defined in the LessThan Comparable requirements.
• ForwardIterator's value type is the same type as LessThanComparable.
For the second version:
• ForwardIterator is a model of Forward Iterator.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• ForwardIterator's value type is the same type as T.
• ForwardIterator's value type is convertible to StrictWeakOrdering's argument type.
Preconditions
For the first version:
• [first, last) is a valid range.
• [first, last) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first, last) such that i precedes j, *j < *i is false.
For the second version:
• [first, last) is a valid range.
• [first, last) is ordered in ascending order according to the function object comp. That is, for every pair of iterators i and j in [first, last) such that i precedes j, comp(*j, *i) is false.
Complexity
The number of comparisons is logarithmic: at most log(last – first) + 1. If ForwardIterator is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last – first. [3]
Example
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 off-the-end." << 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 off-the-end.
Searching for 9. Result: index = 7, which is off-the-end.
Searching for 10. Result: index = 7, which is off-the-end.
Notes
[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.
See also
lower_bound, equal_range, binary_search
- lower_bound
- Совет 45. Различайте алгоритмы count, find, binary_search, lower_bound, upper_bound и equal_range
- Класс BoundedObjectABC
- Lesson 6: Marshaling Data across Boundaries
- Bound for Success
- Prometheus Unbound
- Пример 12-14. toupper: Преобразование символов в верхний регистр.
- Upper Edges
- Time-bound – цели со сроком