...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<_,_> > 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` | 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 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` . |

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

Algorithms, `sort`

, `upper_bound`

Table of Contents

Last edited March 10, 2003 5:43 am