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

   1 .. Algorithms/Querying Algorithms//upper_bound |70
   2
   3 upper_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 upper_bound
  17     {
  18         typedef |unspecified| type;
  19     };
  20
  21
  22
  23 Description
  24 -----------
  25
  26 Returns the last 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/upper_bound.hpp>
  36
  37
  38
  39 Parameters
  40 ----------
  41
  42 +---------------+-------------------------------+-----------------------------------+
  43 | Parameter     | Requirement                   | Description                       |
  44 +===============+===============================+===================================+
  45 |``Sequence``   | |Forward Sequence|            | A sorted sequence to search in.   |
  46 +---------------+-------------------------------+-----------------------------------+
  47 |``T``          | Any type                      | A type to search a position for.  |
  48 +---------------+-------------------------------+-----------------------------------+
  49 |``Pred``       | Binary |Lambda Expression|    | A search criteria.                |
  50 +---------------+-------------------------------+-----------------------------------+
  51
  52
  53 Expression semantics
  54 --------------------
  55
  56 For any sorted |Forward Sequence| ``s``, binary |Lambda Expression| ``pred``, and
  57 arbitrary type ``x``:
  58
  59
  60 .. parsed-literal::
  61
  62     typedef upper_bound< s,x,pred >::type i;
  63
  64 :Return type:
  65     |Forward Iterator|
  66
  67 :Semantics:
  68     ``i`` is the furthermost iterator in |begin/end<s>| such that, for every iterator
  69     ``j`` in ``[begin<s>::type, i)``,
  70
  71     .. parsed-literal::
  72
  73         apply< pred, x, deref<j>::type >::type::value == false
  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 upper_bound< numbers, int_<3> >::type iter;
  92
  93     BOOST_MPL_ASSERT_RELATION(
  94           (distance< begin<numbers>::type,iter >::value), ==, 5
  95         );
  96
  97     BOOST_MPL_ASSERT_RELATION( deref<iter>::type::value, ==, 5 );
  98
  99
 100 See also
 101 --------
 102
 103 |Querying Algorithms|, |lower_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)