lower_bound

Synopsis

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

Description

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

Definition

#include "boost/mpl/lower_bound.hpp"

Parameters

Expression semantics

Expression	Expression type	Precondition	Semantics	Postcondition
typedef lower_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, j::type, T >::type::value == true.

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 lower_bound< numbers, int_<3> >::type iter;
BOOST_STATIC_ASSERT((distance< begin<numbers>::type,iter >::type::value == 2));
BOOST_STATIC_ASSERT(iter::type::value == 3);

See also

Algorithms, sort, upper_bound