


Function template reverse_string_sort

boost::sort::spreadsort::reverse_string_sort — String sort algorithm using random access iterators, allowing character-type overloads.


// In header: <boost/sort/spreadsort/string_sort.hpp>

template<typename RandomAccessIter, typename Compare, 
         typename Unsigned_char_type> 
  void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, 
                           Compare comp, Unsigned_char_type unused);


(All variants fall back to std::sort if the data size is too small, < detail::min_sort_size).

integer_sort is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than std::sort for large tests (>=100kB).
Worst-case performance is O(N * (lg(range)/s + s)) , so integer_sort is asymptotically faster than pure comparison-based algorithms. s is max_splits, which defaults to 11, so its worst-case with default settings for 32-bit integers is O(N * ((32/11) slow radix-based iterations fast comparison-based iterations).

Some performance plots of runtime vs. n and log(range) are provided:

[Warning] 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.

Invalid arguments cause undefined behaviour.

[Note] Note

spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.

The lesser of O(N*log(N)) comparisons and O(N*log(K/S + S)) operations worst-case, where:

* N is last - first,

* K is the log of the range in bits (32 for 32-bit integers using their full range),

* S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).



A binary functor that returns whether the first element passed to it should go before the second in order.


Iterator pointer to first element.


Iterator pointing to one beyond the end of data.


value with the same type as the result of the [] operator, defining the Unsigned_char_type. The actual value is unused.

Template Parameters:


Random access iterator


Unsigned character type used for string.


[first, last) is a valid range.

RandomAccessIter value_type is mutable.

RandomAccessIter value_type is LessThanComparable

RandomAccessIter value_type supports the operator>>, which returns an integer-type right-shifted a specified number of bits.


The elements in the range [first, last) are sorted in ascending order.




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.