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

Click here to view the latest version of this page.
Front Page / Algorithms / Querying Algorithms / upper_bound



      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 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 upper_bound< s,x,pred >::type i; 
Return type:Forward Iterator

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, x, deref<j>::type >::type::value == false 


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 upper_bound< numbers, int_<3> >::type iter;

      (distance< begin<numbers>::type,iter >::value), ==, 5

BOOST_MPL_ASSERT_RELATION( deref<iter>::type::value, ==, 5 );

See also

Querying Algorithms, lower_bound, find, find_if, min_element