...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
template< typename Sequence , typename T , typename Pred = less<_1,_2> > struct upper_bound { typedef unspecified type; };
Returns the last position in the sorted Sequence
where T
could be inserted without violating the ordering.
#include "boost/mpl/upper_bound.hpp"
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 | 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 . |
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
.
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);
Algorithms, sort
, lower_bound