• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1.. Algorithms/Querying Algorithms//upper_bound |70
2
3upper_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 upper_bound
17    {
18        typedef |unspecified| type;
19    };
20
21
22
23Description
24-----------
25
26Returns the last 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/upper_bound.hpp>
36
37
38
39Parameters
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
53Expression semantics
54--------------------
55
56For any sorted |Forward Sequence| ``s``, binary |Lambda Expression| ``pred``, and
57arbitrary 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
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 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
100See 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)
109