Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext
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:

For the predicate versions:

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).


PrevUpHomeNext