1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Function template reverse_string_sort</title>
<link rel="stylesheet" href="../../../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.78.1">
<link rel="home" href="../../../index.html" title="Boost.Sort">
<link rel="up" href="../../../header/boost/sort/spreadsort/string_sort_hpp.html" title="Header <boost/sort/spreadsort/string_sort.hpp>">
<link rel="prev" href="reverse_string_idp48055200.html" title="Function template reverse_string_sort">
<link rel="next" href="string_sort_idp48110368.html" title="Function template string_sort">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="reverse_string_idp48055200.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../../../header/boost/sort/spreadsort/string_sort_hpp.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="string_sort_idp48110368.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="refentry">
<a name="boost.sort.spreadsort.reverse_string_idp48083936"></a><div class="titlepage"></div>
<div class="refnamediv">
<h2><span class="refentrytitle">Function template reverse_string_sort</span></h2>
<p>boost::sort::spreadsort::reverse_string_sort — String sort algorithm using random access iterators, wraps using default of <code class="computeroutput">unsigned</code> char. </p>
</div>
<h2 xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class="refsynopsisdiv-title">Synopsis</h2>
<div xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class="refsynopsisdiv"><pre class="synopsis"><span class="comment">// In header: <<a class="link" href="../../../header/boost/sort/spreadsort/string_sort_hpp.html" title="Header <boost/sort/spreadsort/string_sort.hpp>">boost/sort/spreadsort/string_sort.hpp</a>>
</span>
<span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> RandomAccessIter<span class="special">,</span> <span class="keyword">typename</span> Compare<span class="special">></span>
<span class="keyword">void</span> <span class="identifier">reverse_string_sort</span><span class="special">(</span><span class="identifier">RandomAccessIter</span> first<span class="special">,</span> <span class="identifier">RandomAccessIter</span> last<span class="special">,</span>
<span class="identifier">Compare</span> comp<span class="special">)</span><span class="special">;</span></pre></div>
<div class="refsect1">
<a name="idp93600832"></a><h2>Description</h2>
<p>(All variants fall back to <code class="computeroutput">std::sort</code> if the data size is too small, < <code class="computeroutput">detail::min_sort_size</code>).</p>
<p><code class="computeroutput">integer_sort</code> is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than <code class="computeroutput">std::sort</code> for large tests (>=100kB).<br>
Worst-case performance is <span class="emphasis"><em> O(N * (lg(range)/s + s)) </em></span>, so <code class="computeroutput">integer_sort</code> is asymptotically faster than pure comparison-based algorithms. <code class="computeroutput">s</code> is <code class="computeroutput">max_splits</code>, which defaults to 11, so its worst-case with default settings for 32-bit integers is <span class="emphasis"><em> O(N * ((32/11) </em></span> slow radix-based iterations fast comparison-based iterations).<br>
<br>
Some performance plots of runtime vs. n and log(range) are provided:<br>
<a href="../../../../../doc/graph/windows_integer_sort.htm" target="_top">windows_integer_sort</a> <br>
<a href="../../../../../doc/graph/osx_integer_sort.htm" target="_top">osx_integer_sort</a></p>
<p>
</p>
<div class="warning"><table border="0" summary="Warning">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Warning]" src="../../../../../../../doc/src/images/warning.png"></td>
<th align="left">Warning</th>
</tr>
<tr><td align="left" valign="top"><p>Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. </p></td></tr>
</table></div>
<p>
</p>
<div class="warning"><table border="0" summary="Warning">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Warning]" src="../../../../../../../doc/src/images/warning.png"></td>
<th align="left">Warning</th>
</tr>
<tr><td align="left" valign="top"><p>Invalid arguments cause undefined behaviour. </p></td></tr>
</table></div>
<p>
</p>
<div class="note"><table border="0" summary="Note">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../../../../../doc/src/images/note.png"></td>
<th align="left">Note</th>
</tr>
<tr><td align="left" valign="top"><p><code class="computeroutput">spreadsort</code> function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.</p></td></tr>
</table></div>
<p>
</p>
<p>The lesser of <span class="emphasis"><em> O(N*log(N)) </em></span> comparisons and <span class="emphasis"><em> O(N*log(K/S + S)) </em></span>operations worst-case, where: </p>
<p>
</p>
<p>* N is <code class="computeroutput">last</code> - <code class="computeroutput">first</code>, </p>
<p>
</p>
<p>* K is the log of the range in bits (32 for 32-bit integers using their full range), </p>
<p>
</p>
<p>* S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). </p>
<p>
</p>
<div class="variablelist"><table border="0" class="variablelist compact">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term">Parameters:</span></p></td>
<td><div class="variablelist"><table border="0" class="variablelist compact">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><code class="computeroutput">comp</code></span></p></td>
<td><p>A binary functor that returns whether the first element passed to it should go before the second in order.</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="computeroutput">first</code></span></p></td>
<td><p>Iterator pointer to first element. </p></td>
</tr>
<tr>
<td><p><span class="term"><code class="computeroutput">last</code></span></p></td>
<td><p>Iterator pointing to one beyond the end of data. </p></td>
</tr>
</tbody>
</table></div></td>
</tr>
<tr>
<td><p><span class="term">Requires:</span></p></td>
<td><p>[<code class="computeroutput">first</code>, <code class="computeroutput">last</code>) is a valid range. </p></td>
</tr>
<tr>
<td><p><span class="term">Requires:</span></p></td>
<td><p><code class="computeroutput">RandomAccessIter</code> <code class="computeroutput">value_type</code> is mutable. </p></td>
</tr>
<tr>
<td><p><span class="term">Requires:</span></p></td>
<td><p><code class="computeroutput">RandomAccessIter</code> <code class="computeroutput">value_type</code> is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable" target="_top">LessThanComparable</a> </p></td>
</tr>
<tr>
<td><p><span class="term">Requires:</span></p></td>
<td><p><code class="computeroutput">RandomAccessIter</code> <code class="computeroutput">value_type</code> supports the <code class="computeroutput">operator>></code>, which returns an integer-type right-shifted a specified number of bits. </p></td>
</tr>
<tr>
<td><p><span class="term">Postconditions:</span></p></td>
<td><p>The elements in the range [<code class="computeroutput">first</code>, <code class="computeroutput">last</code>) are sorted in ascending order.</p></td>
</tr>
<tr>
<td><p><span class="term">Returns:</span></p></td>
<td><p><code class="computeroutput">void</code>.</p></td>
</tr>
<tr>
<td><p><span class="term">Throws:</span></p></td>
<td>std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.</td>
</tr>
</tbody>
</table></div>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2014 Steven Ross<p>
Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost
Software License, Version 1.0</a>.
</p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="reverse_string_idp48055200.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../../../header/boost/sort/spreadsort/string_sort_hpp.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="string_sort_idp48110368.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
|
