upper_bound

Prototype

template<
    class ForwardRange,
    class Value
    >
typename range_iterator<ForwardRange>::type
upper_bound(ForwardRange& rng, Value val);

template<
    range_return_value re,
    class ForwardRange,
    class Value
    >
typename range_return<ForwardRange, re>::type
upper_bound(ForwardRange& rng, Value val);

template<
    class ForwardRange,
    class Value,
    class SortPredicate
    >
typename range_iterator<ForwardRange>::type
upper_bound(ForwardRange& rng, Value val, SortPredicate pred);

template<
    range_return_value re,
    class ForwardRange,
    class Value,
    class SortPredicate
    >
typename range_return<ForwardRange,re>::type
upper_bound(ForwardRange& rng, Value val, SortPredicate pred);

Description

The versions of upper_bound that return an iterator, returns the first iterator in the range rng such that: without predicate - val < *i is true, with predicate - pred(val, *i) is true.

end(rng) is returned if no such iterator exists.

The versions of upper_bound that return a range_return, defines found in the same manner as the returned iterator described above.

Definition

Defined in the header file boost/range/algorithm/upper_bound.hpp

Requirements

For the non-predicate versions:

ForwardRange is a model of the Forward Range Concept.
Value is a model of the LessThanComparableConcept.
The ordering of objects of type Value is a strict weak ordering, as defined in the LessThanComparableConcept requirements.
ForwardRange's value type is the same type as Value.

For the predicate versions:

ForwardRange is a model of the Forward Range Concept.
BinaryPredicate is a model of the StrictWeakOrderingConcept.
ForwardRange's value type is the same type as Value.
ForwardRange's value type is convertible to both of BinaryPredicate's argument types.

Precondition:

For the non-predicate versions:

rng is sorted in ascending order according to operator<.

For the predicate versions:

rng is sorted in ascending order according to pred.

Complexity

For ranges that model the Random Access Range Concept the complexity is O(log N), where N is distance(rng). For all other range types the complexity is O(N).