...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 { typedef unspecified type; };
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: | 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 log2( 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 );