# upper_bound

### Synopsis

    template<
          typename Sequence
        , typename T
        , typename Pred = less<_1,_2>
        >
    struct upper_bound
    {
        typedef unspecified type;
    };

### Description

Returns the last position in the sorted `Sequence` where `T` could be inserted without violating the ordering.

### Definition

    #include "boost/mpl/upper_bound.hpp"

### Parameters

Parameter | Requirement | Description
--- | --- | ---
`Sequence` | A model of Forward Sequence | A sorted sequence.
`T` | A type | A type to search the position for.
`Pred` | A model of binary Predicate [Lambda Expression] | A sort criteria.

### Expression semantics

Expression | Expression type | Precondition | Semantics | Postcondition
--- | --- | --- | --- | ---
`typedef upper_bound< Sequence,T,Pred >::type i;` | A model of Forward Iterator |  | `i` is the furthermost iterator in `[begin<Sequence>::type, end<Sequence>::type)` such that, for every iterator `j` in `[begin<Sequence>::type, i)`, `apply< lambda<Pred>::type, T, j::type >::type::value == false`. |

### Complexity

The number of comparisons is logarithmic: at most `log(size<Sequence>::type::value) + 1`. If `Sequence` is a Random Access Sequence then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to `size<Sequence>::type::value`.

### Example

    typedef list_c<int,1,2,3,3,3,5,8> numbers;
    typedef upper_bound< numbers, int_<3> >::type iter;
    BOOST_STATIC_ASSERT((distance< begin<numbers>::type,iter >::type::value == 5));
    BOOST_STATIC_ASSERT(iter::type::value == 5);

### See also

Algorithms, `sort`, `lower_bound`

Table of Contents
Last edited March 10, 2003 5:44 am