]>
Commit | Line | Data |
---|---|---|
1 | //Templated hybrid string_sort | |
2 | ||
3 | // Copyright Steven J. Ross 2001 - 2009. | |
4 | // Distributed under the Boost Software License, Version 1.0. | |
5 | // (See accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt) | |
7 | ||
8 | // See http://www.boost.org/libs/sort/ for library home page. | |
9 | ||
10 | /* | |
11 | Some improvements suggested by: | |
12 | Phil Endecott and Frank Gennari | |
13 | */ | |
14 | ||
15 | #ifndef BOOST_STRING_SORT_HPP | |
16 | #define BOOST_STRING_SORT_HPP | |
17 | #include <algorithm> | |
18 | #include <vector> | |
19 | #include <cstring> | |
20 | #include <limits> | |
21 | #include <boost/static_assert.hpp> | |
22 | #include <boost/sort/spreadsort/detail/constants.hpp> | |
23 | #include <boost/sort/spreadsort/detail/string_sort.hpp> | |
24 | ||
25 | namespace boost { | |
26 | namespace sort { | |
27 | namespace spreadsort { | |
28 | ||
29 | /*! \brief String sort algorithm using random access iterators, allowing character-type overloads.\n | |
30 | (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size). | |
31 | ||
32 | \details @c string_sort is a fast templated in-place hybrid radix/comparison algorithm, | |
33 | which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n | |
34 | \par | |
35 | Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, | |
36 | so @c integer_sort is asymptotically faster | |
37 | than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, | |
38 | so its worst-case with default settings for 32-bit integers is | |
39 | <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n | |
40 | Some performance plots of runtime vs. n and log(range) are provided:\n | |
41 | <a href="../../doc/graph/windows_string_sort.htm"> windows_string_sort</a>\n | |
42 | <a href="../../doc/graph/osx_string_sort.htm"> osx_string_sort</a> | |
43 | ||
44 | \tparam RandomAccessIter <a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> | |
45 | \tparam Unsigned_char_type Unsigned character type used for string. | |
46 | \param[in] first Iterator pointer to first element. | |
47 | \param[in] last Iterator pointing to one beyond the end of data. | |
48 | \param[in] unused value with the same type as the result of the [] operator, defining the Unsigned_char_type. The actual value is unused. | |
49 | ||
50 | \pre [@c first, @c last) is a valid range. | |
51 | \pre @c RandomAccessIter @c value_type is mutable. | |
52 | \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> | |
53 | \pre @c RandomAccessIter @c value_type supports the @c operator>>, | |
54 | which returns an integer-type right-shifted a specified number of bits. | |
55 | \post The elements in the range [@c first, @c last) are sorted in ascending order. | |
56 | ||
57 | \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), | |
58 | the right shift, subtraction of right-shifted elements, functors, | |
59 | or any operations on iterators throw. | |
60 | ||
61 | \warning 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. | |
62 | \warning Invalid arguments cause undefined behaviour. | |
63 | \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, | |
64 | enabling faster generic-programming. | |
65 | ||
66 | \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: | |
67 | \remark * N is @c last - @c first, | |
68 | \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), | |
69 | \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). | |
70 | ||
71 | */ | |
72 | ||
73 | template <class RandomAccessIter, class Unsigned_char_type> | |
74 | inline void string_sort(RandomAccessIter first, RandomAccessIter last, | |
75 | Unsigned_char_type unused) | |
76 | { | |
77 | //Don't sort if it's too small to optimize | |
78 | if (last - first < detail::min_sort_size) | |
79 | std::sort(first, last); | |
80 | else | |
81 | detail::string_sort(first, last, unused); | |
82 | } | |
83 | ||
84 | ||
85 | /*! \brief String sort algorithm using random access iterators, wraps using default of unsigned char. | |
86 | (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size). | |
87 | ||
88 | \details @c string_sort is a fast templated in-place hybrid radix/comparison algorithm, | |
89 | which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n | |
90 | Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, | |
91 | so @c integer_sort is asymptotically faster | |
92 | than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, | |
93 | so its worst-case with default settings for 32-bit integers is | |
94 | <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n | |
95 | Some performance plots of runtime vs. n and log(range) are provided:\n | |
96 | <a href="../../doc/graph/windows_string_sort.htm"> windows_string_sort</a> | |
97 | \n | |
98 | <a href="../../doc/graph/osx_string_sort.htm"> osx_string_sort</a> | |
99 | ||
100 | \param[in] first Iterator pointer to first element. | |
101 | \param[in] last Iterator pointing to one beyond the end of data. | |
102 | ||
103 | \pre [@c first, @c last) is a valid range. | |
104 | \pre @c RandomAccessIter @c value_type is mutable. | |
105 | \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> | |
106 | \pre @c RandomAccessIter @c value_type supports the @c operator>>, | |
107 | which returns an integer-type right-shifted a specified number of bits. | |
108 | \post The elements in the range [@c first, @c last) are sorted in ascending order. | |
109 | ||
110 | \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), | |
111 | the right shift, subtraction of right-shifted elements, functors, | |
112 | or any operations on iterators throw. | |
113 | ||
114 | \warning 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. | |
115 | \warning Invalid arguments cause undefined behaviour. | |
116 | \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, | |
117 | enabling faster generic-programming. | |
118 | ||
119 | \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: | |
120 | \remark * N is @c last - @c first, | |
121 | \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), | |
122 | \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). | |
123 | ||
124 | */ | |
125 | template <class RandomAccessIter> | |
126 | inline void string_sort(RandomAccessIter first, RandomAccessIter last) | |
127 | { | |
128 | unsigned char unused = '\0'; | |
129 | string_sort(first, last, unused); | |
130 | } | |
131 | ||
132 | ||
133 | /*! \brief String sort algorithm using random access iterators, allowing character-type overloads. | |
134 | ||
135 | (All variants fall back to @c std::sort if the data size is too small, < detail::min_sort_size). | |
136 | ||
137 | \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, | |
138 | which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n | |
139 | Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, | |
140 | so @c integer_sort is asymptotically faster | |
141 | than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, | |
142 | so its worst-case with default settings for 32-bit integers is | |
143 | <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n | |
144 | Some performance plots of runtime vs. n and log(range) are provided:\n | |
145 | <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a> | |
146 | \n | |
147 | <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> | |
148 | ||
149 | ||
150 | \tparam RandomAccessIter <a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> | |
151 | \tparam Comp Functor type to use for comparison. | |
152 | \tparam Unsigned_char_type Unsigned character type used for string. | |
153 | ||
154 | \param[in] first Iterator pointer to first element. | |
155 | \param[in] last Iterator pointing to one beyond the end of data. | |
156 | \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order. | |
157 | \param[in] unused value with the same type as the result of the [] operator, defining the Unsigned_char_type. The actual value is unused. | |
158 | ||
159 | \pre [@c first, @c last) is a valid range. | |
160 | \pre @c RandomAccessIter @c value_type is mutable. | |
161 | \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> | |
162 | \pre @c RandomAccessIter @c value_type supports the @c operator>>, | |
163 | which returns an integer-type right-shifted a specified number of bits. | |
164 | \post The elements in the range [@c first, @c last) are sorted in ascending order. | |
165 | ||
166 | \return @c void. | |
167 | ||
168 | \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), | |
169 | the right shift, subtraction of right-shifted elements, functors, | |
170 | or any operations on iterators throw. | |
171 | ||
172 | \warning 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. | |
173 | \warning Invalid arguments cause undefined behaviour. | |
174 | \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, | |
175 | enabling faster generic-programming. | |
176 | ||
177 | \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: | |
178 | \remark * N is @c last - @c first, | |
179 | \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), | |
180 | \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). | |
181 | */ | |
182 | template <class RandomAccessIter, class Compare, class Unsigned_char_type> | |
183 | inline void reverse_string_sort(RandomAccessIter first, | |
184 | RandomAccessIter last, Compare comp, Unsigned_char_type unused) | |
185 | { | |
186 | //Don't sort if it's too small to optimize. | |
187 | if (last - first < detail::min_sort_size) | |
188 | std::sort(first, last, comp); | |
189 | else | |
190 | detail::reverse_string_sort(first, last, unused); | |
191 | } | |
192 | ||
193 | ||
194 | /*! \brief String sort algorithm using random access iterators, wraps using default of @c unsigned char. | |
195 | ||
196 | (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size). | |
197 | ||
198 | \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, | |
199 | which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n | |
200 | Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, | |
201 | so @c integer_sort is asymptotically faster | |
202 | than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, | |
203 | so its worst-case with default settings for 32-bit integers is | |
204 | <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n | |
205 | Some performance plots of runtime vs. n and log(range) are provided:\n | |
206 | <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a> | |
207 | \n | |
208 | <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> | |
209 | ||
210 | \param[in] first Iterator pointer to first element. | |
211 | \param[in] last Iterator pointing to one beyond the end of data. | |
212 | \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order. | |
213 | ||
214 | \pre [@c first, @c last) is a valid range. | |
215 | \pre @c RandomAccessIter @c value_type is mutable. | |
216 | \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> | |
217 | \pre @c RandomAccessIter @c value_type supports the @c operator>>, | |
218 | which returns an integer-type right-shifted a specified number of bits. | |
219 | \post The elements in the range [@c first, @c last) are sorted in ascending order. | |
220 | ||
221 | \return @c void. | |
222 | ||
223 | \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), | |
224 | the right shift, subtraction of right-shifted elements, functors, | |
225 | or any operations on iterators throw. | |
226 | ||
227 | \warning 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. | |
228 | \warning Invalid arguments cause undefined behaviour. | |
229 | \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, | |
230 | enabling faster generic-programming. | |
231 | ||
232 | \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: | |
233 | \remark * N is @c last - @c first, | |
234 | \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), | |
235 | \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). | |
236 | */ | |
237 | template <class RandomAccessIter, class Compare> | |
238 | inline void reverse_string_sort(RandomAccessIter first, | |
239 | RandomAccessIter last, Compare comp) | |
240 | { | |
241 | unsigned char unused = '\0'; | |
242 | reverse_string_sort(first, last, comp, unused); | |
243 | } | |
244 | ||
245 | ||
246 | /*! \brief String sort algorithm using random access iterators, wraps using default of @c unsigned char. | |
247 | ||
248 | (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size). | |
249 | ||
250 | \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, | |
251 | which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n | |
252 | Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, | |
253 | so @c integer_sort is asymptotically faster | |
254 | than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, | |
255 | so its worst-case with default settings for 32-bit integers is | |
256 | <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n | |
257 | Some performance plots of runtime vs. n and log(range) are provided:\n | |
258 | <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a> | |
259 | \n | |
260 | <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> | |
261 | ||
262 | \param[in] first Iterator pointer to first element. | |
263 | \param[in] last Iterator pointing to one beyond the end of data. | |
264 | \param[in] getchar Bracket functor equivalent to @c operator[], taking a number corresponding to the character offset. | |
265 | \param[in] length Functor to get the length of the string in characters. | |
266 | ||
267 | \pre [@c first, @c last) is a valid range. | |
268 | \pre @c RandomAccessIter @c value_type is mutable. | |
269 | \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> | |
270 | \pre @c RandomAccessIter @c value_type supports the @c operator>>, | |
271 | which returns an integer-type right-shifted a specified number of bits. | |
272 | \post The elements in the range [@c first, @c last) are sorted in ascending order. | |
273 | ||
274 | \return @c void. | |
275 | ||
276 | \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), | |
277 | the right shift, subtraction of right-shifted elements, functors, | |
278 | or any operations on iterators throw. | |
279 | ||
280 | \warning 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. | |
281 | \warning Invalid arguments cause undefined behaviour. | |
282 | \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, | |
283 | enabling faster generic-programming. | |
284 | ||
285 | \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: | |
286 | \remark * N is @c last - @c first, | |
287 | \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), | |
288 | \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). | |
289 | ||
290 | */ | |
291 | template <class RandomAccessIter, class Get_char, class Get_length> | |
292 | inline void string_sort(RandomAccessIter first, RandomAccessIter last, | |
293 | Get_char getchar, Get_length length) | |
294 | { | |
295 | //Don't sort if it's too small to optimize | |
296 | if (last - first < detail::min_sort_size) | |
297 | std::sort(first, last); | |
298 | else { | |
299 | //skipping past empties, which allows us to get the character type | |
300 | //.empty() is not used so as not to require a user declaration of it | |
301 | while (!length(*first)) { | |
302 | if (++first == last) | |
303 | return; | |
304 | } | |
305 | detail::string_sort(first, last, getchar, length, getchar((*first), 0)); | |
306 | } | |
307 | } | |
308 | ||
309 | ||
310 | ||
311 | /*! \brief String sort algorithm using random access iterators, wraps using default of @c unsigned char. | |
312 | ||
313 | (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size). | |
314 | ||
315 | \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, | |
316 | which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n | |
317 | Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, | |
318 | so @c integer_sort is asymptotically faster | |
319 | than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, | |
320 | so its worst-case with default settings for 32-bit integers is | |
321 | <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n | |
322 | Some performance plots of runtime vs. n and log(range) are provided:\n | |
323 | <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a> | |
324 | \n | |
325 | <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> | |
326 | ||
327 | ||
328 | \param[in] first Iterator pointer to first element. | |
329 | \param[in] last Iterator pointing to one beyond the end of data. | |
330 | \param[in] getchar Bracket functor equivalent to @c operator[], taking a number corresponding to the character offset. | |
331 | \param[in] length Functor to get the length of the string in characters. | |
332 | \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order. | |
333 | ||
334 | ||
335 | \pre [@c first, @c last) is a valid range. | |
336 | \pre @c RandomAccessIter @c value_type is mutable. | |
337 | \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> | |
338 | \post The elements in the range [@c first, @c last) are sorted in ascending order. | |
339 | ||
340 | \return @c void. | |
341 | ||
342 | \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), | |
343 | the right shift, subtraction of right-shifted elements, functors, | |
344 | or any operations on iterators throw. | |
345 | ||
346 | \warning 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. | |
347 | \warning Invalid arguments cause undefined behaviour. | |
348 | \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, | |
349 | enabling faster generic-programming. | |
350 | ||
351 | \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: | |
352 | \remark * N is @c last - @c first, | |
353 | \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), | |
354 | \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). | |
355 | ||
356 | */ | |
357 | template <class RandomAccessIter, class Get_char, class Get_length, | |
358 | class Compare> | |
359 | inline void string_sort(RandomAccessIter first, RandomAccessIter last, | |
360 | Get_char getchar, Get_length length, Compare comp) | |
361 | { | |
362 | //Don't sort if it's too small to optimize | |
363 | if (last - first < detail::min_sort_size) | |
364 | std::sort(first, last, comp); | |
365 | else { | |
366 | //skipping past empties, which allows us to get the character type | |
367 | //.empty() is not used so as not to require a user declaration of it | |
368 | while (!length(*first)) { | |
369 | if (++first == last) | |
370 | return; | |
371 | } | |
372 | detail::string_sort(first, last, getchar, length, comp, | |
373 | getchar((*first), 0)); | |
374 | } | |
375 | } | |
376 | ||
377 | ||
378 | /*! \brief Reverse String sort algorithm using random access iterators. | |
379 | ||
380 | (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size). | |
381 | ||
382 | \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, | |
383 | which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n | |
384 | Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, | |
385 | so @c integer_sort is asymptotically faster | |
386 | than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, | |
387 | so its worst-case with default settings for 32-bit integers is | |
388 | <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n | |
389 | Some performance plots of runtime vs. n and log(range) are provided:\n | |
390 | <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a> | |
391 | \n | |
392 | <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> | |
393 | ||
394 | ||
395 | \param[in] first Iterator pointer to first element. | |
396 | \param[in] last Iterator pointing to one beyond the end of data. | |
397 | \param[in] getchar Bracket functor equivalent to @c operator[], taking a number corresponding to the character offset. | |
398 | \param[in] length Functor to get the length of the string in characters. | |
399 | \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order. | |
400 | ||
401 | ||
402 | \pre [@c first, @c last) is a valid range. | |
403 | \pre @c RandomAccessIter @c value_type is mutable. | |
404 | \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> | |
405 | \post The elements in the range [@c first, @c last) are sorted in ascending order. | |
406 | ||
407 | \return @c void. | |
408 | ||
409 | \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), | |
410 | the right shift, subtraction of right-shifted elements, functors, | |
411 | or any operations on iterators throw. | |
412 | ||
413 | \warning 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. | |
414 | \warning Invalid arguments cause undefined behaviour. | |
415 | \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, | |
416 | enabling faster generic-programming. | |
417 | ||
418 | \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: | |
419 | \remark * N is @c last - @c first, | |
420 | \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), | |
421 | \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). | |
422 | ||
423 | */ | |
424 | template <class RandomAccessIter, class Get_char, class Get_length, | |
425 | class Compare> | |
426 | inline void reverse_string_sort(RandomAccessIter first, | |
427 | RandomAccessIter last, Get_char getchar, Get_length length, Compare comp) | |
428 | { | |
429 | //Don't sort if it's too small to optimize | |
430 | if (last - first < detail::min_sort_size) | |
431 | std::sort(first, last, comp); | |
432 | else { | |
433 | //skipping past empties, which allows us to get the character type | |
434 | //.empty() is not used so as not to require a user declaration of it | |
435 | while (!length(*(--last))) { | |
436 | //If there is just one non-empty at the beginning, this is sorted | |
437 | if (first == last) | |
438 | return; | |
439 | } | |
440 | //making last just after the end of the non-empty part of the array | |
441 | detail::reverse_string_sort(first, last + 1, getchar, length, comp, | |
442 | getchar((*last), 0)); | |
443 | } | |
444 | } | |
445 | } | |
446 | } | |
447 | } | |
448 | ||
449 | #endif |