Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

The MPL Reference Manual: lower_bound
Prev Next | Back Along | Up Home | Full TOC Front Page / Algorithms / Querying Algorithms / lower_bound

lower_bound

Synopsis

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

Description

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

Parameters

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.

Expression semantics

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

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

Forward Iterator.
Semantics:

i is the furthermost iterator in [begin::type, end::type) such that, for every iterator j in [begin::type, i),

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

Complexity

The number of comparisons is logarithmic: at most log2( size::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::value.

Example

typedef vector_c numbers;
typedef lower_bound< numbers, int_<3> >::type iter;

BOOST_MPL_ASSERT_RELATION(
      (distance< begin::type,iter >::value), ==, 2
    );

BOOST_MPL_ASSERT_RELATION( deref::type::value, ==, 3 );
Prev Next | Back Along | Up Home | Full TOC
Copyright © 2001-2009 Aleksey Gurtovoy and David Abrahams
Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)