1.. Algorithms/Querying Algorithms//lower_bound |60 2 3lower_bound 4=========== 5 6Synopsis 7-------- 8 9.. parsed-literal:: 10 11 template< 12 typename Sequence 13 , typename T 14 , typename Pred = less<_1,_2> 15 > 16 struct lower_bound 17 { 18 typedef |unspecified| type; 19 }; 20 21 22 23Description 24----------- 25 26Returns the first position in the sorted ``Sequence`` where ``T`` could be inserted without 27violating the ordering. 28 29 30Header 31------ 32 33.. parsed-literal:: 34 35 #include <boost/mpl/lower_bound.hpp> 36 37 38Parameters 39---------- 40 41+---------------+-------------------------------+-----------------------------------+ 42| Parameter | Requirement | Description | 43+===============+===============================+===================================+ 44|``Sequence`` | |Forward Sequence| | A sorted sequence to search in. | 45+---------------+-------------------------------+-----------------------------------+ 46|``T`` | Any type | A type to search a position for. | 47+---------------+-------------------------------+-----------------------------------+ 48|``Pred`` | Binary |Lambda Expression| | A search criteria. | 49+---------------+-------------------------------+-----------------------------------+ 50 51 52Expression semantics 53-------------------- 54 55For any sorted |Forward Sequence| ``s``, binary |Lambda Expression| ``pred``, and 56arbitrary type ``x``: 57 58 59.. parsed-literal:: 60 61 typedef lower_bound< s,x,pred >::type i; 62 63:Return type: 64 |Forward Iterator|. 65 66:Semantics: 67 ``i`` is the furthermost iterator in |begin/end<s>| such that, for every iterator 68 ``j`` in [``begin<s>::type``, ``i``), 69 70 .. parsed-literal:: 71 72 apply< pred, deref<j>::type, x >::type::value == true 73 74 75 76Complexity 77---------- 78 79The number of comparisons is logarithmic: at most log\ :sub:`2`\ ( ``size<s>::value`` ) + 1. 80If ``s`` is a |Random Access Sequence| then the number of steps through the range 81is also logarithmic; otherwise, the number of steps is proportional to 82``size<s>::value``. 83 84 85Example 86------- 87 88.. parsed-literal:: 89 90 typedef vector_c<int,1,2,3,3,3,5,8> numbers; 91 typedef lower_bound< numbers, int_<3> >::type iter; 92 93 BOOST_MPL_ASSERT_RELATION( 94 (distance< begin<numbers>::type,iter >::value), ==, 2 95 ); 96 97 BOOST_MPL_ASSERT_RELATION( deref<iter>::type::value, ==, 3 ); 98 99 100See also 101-------- 102 103|Querying Algorithms|, |upper_bound|, |find|, |find_if|, |min_element| 104 105 106.. copyright:: Copyright � 2001-2009 Aleksey Gurtovoy and David Abrahams 107 Distributed under the Boost Software License, Version 1.0. (See accompanying 108 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 109