• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1.. Algorithms/Transformation Algorithms//sort |95
2
3sort
4====
5
6Synopsis
7--------
8
9.. parsed-literal::
10
11    template<
12          typename Seq
13        , typename Pred = less<_1,_2>
14        , typename In = |unspecified|
15        >
16    struct sort
17    {
18        typedef |unspecified| type;
19    };
20
21
22Description
23-----------
24
25Returns a new sequence of all elements in the range |begin/end<Seq>| sorted according
26to the ordering relation ``Pred``.
27
28|transformation algorithm disclaimer|
29
30
31Header
32------
33
34.. parsed-literal::
35
36    #include <boost/mpl/sort.hpp>
37
38
39Model of
40--------
41
42|Reversible Algorithm|
43
44
45Parameters
46----------
47
48+-------------------+-----------------------------------+-------------------------------+
49| Parameter         | Requirement                       | Description                   |
50+===================+===================================+===============================+
51| ``Seq``           | |Forward Sequence|                | An original sequence.         |
52+-------------------+-----------------------------------+-------------------------------+
53| ``Pred``          | Binary |Lambda Expression|        | An ordering relation.         |
54+-------------------+-----------------------------------+-------------------------------+
55| ``In``            | |Inserter|                        | An inserter.                  |
56+-------------------+-----------------------------------+-------------------------------+
57
58
59Expression semantics
60--------------------
61
62|Semantics disclaimer...| |Reversible Algorithm|.
63
64For any |Forward Sequence| ``s``, a binary |Lambda Expression| ``pred``, and an
65|Inserter| ``in``:
66
67
68.. parsed-literal::
69
70    typedef sort<s,pred,in>::type r;
71
72:Return type:
73    A type.
74
75:Semantics:
76    If ``size<s>::value <= 1``, equivalent to
77
78    .. parsed-literal::
79
80        typedef copy<s,in>::type r;
81
82
83    otherwise equivalent to
84
85    .. parsed-literal::
86
87        typedef back_inserter< vector<> > aux_in;
88        typedef lambda<pred>::type p;
89
90        typedef begin<s>::type pivot;
91        typedef partition<
92              iterator_range< next<pivot>::type, end<s>::type >
93            , apply_wrap2<p,_1,deref<pivot>::type>
94            , aux_in
95            , aux_in
96            >::type partitioned;
97
98        typedef sort<partitioned::first,p,aux_in >::type part1;
99        typedef sort<partitioned::second,p,aux_in >::type part2;
100
101        typedef copy<
102              joint_view<
103                  joint_view<part1,single_view< deref<pivot>::type > >
104                , part2
105                >
106            , in
107            >::type r;
108
109
110Complexity
111----------
112
113Average *O(n log(n))* where *n* == ``size<s>::value``, quadratic at worst.
114
115Example
116-------
117
118.. parsed-literal::
119
120    typedef vector_c<int,3,4,0,-5,8,-1,7> numbers;
121    typedef vector_c<int,-5,-1,0,3,4,7,8> expected;
122    typedef sort<numbers>::type result;
123
124    BOOST_MPL_ASSERT(( equal< result, expected, equal_to<_,_> > ));
125
126
127See also
128--------
129
130|Transformation Algorithms|, |Reversible Algorithm|, |partition|
131
132
133.. copyright:: Copyright �  2001-2009 Aleksey Gurtovoy and David Abrahams
134   Distributed under the Boost Software License, Version 1.0. (See accompanying
135   file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
136