ceph/src/boost/libs/mpl/doc/src/refmanual/lower_bound.rst

   1 .. Algorithms/Querying Algorithms//lower_bound |60
   2
   3 lower_bound
   4 ===========
   5
   6 Synopsis
   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
  23 Description
  24 -----------
  25
  26 Returns the first position in the sorted ``Sequence`` where ``T`` could be inserted without
  27 violating the ordering.
  28
  29
  30 Header
  31 ------
  32
  33 .. parsed-literal::
  34
  35     #include <boost/mpl/lower_bound.hpp>
  36
  37
  38 Parameters
  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
  52 Expression semantics
  53 --------------------
  54
  55 For any sorted |Forward Sequence| ``s``, binary |Lambda Expression| ``pred``, and
  56 arbitrary 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
  76 Complexity
  77 ----------
  78
  79 The number of comparisons is logarithmic: at most log\ :sub:`2`\ ( ``size<s>::value`` ) + 1.
  80 If ``s`` is a |Random Access Sequence| then the number of steps through the range
  81 is also logarithmic; otherwise, the number of steps is proportional to
  82 ``size<s>::value``.
  83
  84
  85 Example
  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
 100 See 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)