...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

Front Page / Algorithms / Querying Algorithms / lower_bound |

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

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

#include <boost/mpl/lower_bound.hpp>

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

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

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

Return type: | |
---|---|

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

The number of comparisons is logarithmic: at most log_{2}( `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`.

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