lower_bound

Synopsis

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

Description

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

Header

#include <boost/mpl/lower_bound.hpp>

Parameters

Parameter	Requirement	Description
`Sequence`	Forward Sequence	A sorted sequence to search in.
`T`	Any type	A type to search a position for.
`Pred`	Binary Lambda Expression	A search criteria.

Expression semantics

For any sorted Forward Sequence s, binary Lambda Expression pred, and arbitrary type x:

typedef lower_bound< s,x,pred >::type i;

Return type: Forward Iterator.

Semantics:

Return type:	Forward Iterator.
Semantics:	`i` is the furthermost iterator in [`begin<s>::type`, `end<s>::type`) such that, for every iterator `j` in [`begin<s>::type`, `i`), apply< pred, deref<j>::type, x >::type::value == true

i is the furthermost iterator in [begin<s>::type, end<s>::type) such that, for every iterator j in [begin<s>::type, i),

apply< pred, deref<j>::type, x >::type::value == true

The number of comparisons is logarithmic: at most log₂( size<s>::value ) + 1. If s 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<s>::value.

Example

typedef vector_c<int,1,2,3,3,3,5,8> numbers;
typedef lower_bound< numbers, int_<3> >::type iter;

BOOST_MPL_ASSERT_RELATION( 
      (distance< begin<numbers>::type,iter >::value), ==, 2
    );

BOOST_MPL_ASSERT_RELATION( deref<iter>::type::value, ==, 3 );