C++ In a Nutshell

Name

upper_bound function template — Finds upper bound for a value’s position in a sorted range using binary search

Synopsis

template<typename FwdIter, typename T>
  FwdIter upper_bound(FwdIter first, FwdIter last, const T& value);
template<typename FwdIter, typename T, typename Compare>
  FwdIter upper_bound(FwdIter first, FwdIter last, const T& value, Compare comp);

The upper_bound function template determines where value belongs in the sorted range [first, last). The return value is an iterator that points to one past the last (rightmost) occurrence of value in the range, if value is present. Otherwise, the iterator points to the last position where you can insert value and preserve the sorted nature of the range.

The first form compares values using the < operator. The second form calls comp(*iter, value).

Figure 13-4 (under equal_range) shows an example of finding the bounds for the value 36. The upper_bound function returns ub as the upper bound of 36 in the given range. Note that it returns ub as the upper bound for all values in the range [36, 41]. For values in the range [19, 35], the upper bound is equal to lb.

Technical Notes

Precondition: !(*(i + 1) < *i) for all i in [first, last - 1).

The upper_bound function template returns first + n, in which n is the highest value in [0, last - first) such that *(first + m) < value is false for all m in [0, n).

Complexity is logarithmic. The number of comparisons is at most log(last - first) + 1. Although the iterator can be a forward iterator, ...