Share via

upper_bound

  • Article

upper_bound

template<class FwdIt, class T>
    FwdIt upper_bound(FwdIt first, FwdIt last, const T& val);
template<class FwdIt, class T, class Pred>
    FwdIt upper_bound(FwdIt first, FwdIt last, const T& val, Pred pr);

The first template function determines the highest value of N in the range [0, last - first) such that, for each M in the range [0, N) the predicate *(first + M) < val is true, where the elements designated by iterators in the range [first, last) form a sequence ordered byoperator<. It then returns first + N. If no such value exists, the function returns last. Thus, the function determines the highest position before which val can be inserted into the sequence and still preserve its ordering.

If FwdIt is a random-access iterator type, the function evaluates the ordering predicate X < Y``ceil(log(last - first)) + 1 times at most. Otherwise, the function evaluates the predicate a number of times proportional to last - first.

The second template function behaves the same, except that it replaces operator<(X, Y) with pr(X, Y).

Sample programs: upper_bound and upper_bound (predicate version).