]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | .. Algorithms/Transformation Algorithms//sort |95 |
2 | ||
3 | sort | |
4 | ==== | |
5 | ||
6 | Synopsis | |
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 | ||
22 | Description | |
23 | ----------- | |
24 | ||
25 | Returns a new sequence of all elements in the range |begin/end<Seq>| sorted according | |
26 | to the ordering relation ``Pred``. | |
27 | ||
28 | |transformation algorithm disclaimer| | |
29 | ||
30 | ||
31 | Header | |
32 | ------ | |
33 | ||
34 | .. parsed-literal:: | |
35 | ||
36 | #include <boost/mpl/sort.hpp> | |
37 | ||
38 | ||
39 | Model of | |
40 | -------- | |
41 | ||
42 | |Reversible Algorithm| | |
43 | ||
44 | ||
45 | Parameters | |
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 | ||
59 | Expression semantics | |
60 | -------------------- | |
61 | ||
62 | |Semantics disclaimer...| |Reversible Algorithm|. | |
63 | ||
64 | For 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 | ||
110 | Complexity | |
111 | ---------- | |
112 | ||
113 | Average *O(n log(n))* where *n* == ``size<s>::value``, quadratic at worst. | |
114 | ||
115 | Example | |
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 | ||
127 | See also | |
128 | -------- | |
129 | ||
130 | |Transformation Algorithms|, |Reversible Algorithm|, |partition| | |
131 | ||
132 | ||
133 |