Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for an old version of boost. Click here for the latest Boost documentation.
PrevUpHomeNext

Function template reverse_string_sort

boost::sort::spreadsort::reverse_string_sort — String sort algorithm using random access iterators, wraps using default of unsigned char.

Synopsis

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


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

Description

(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:
windows_integer_sort
osx_integer_sort

[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).

Parameters:

comp

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

first

Iterator pointer to first element.

last

Iterator pointing to one beyond the end of data.

Requires:

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

Postconditions:

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

Returns:

void.

Throws:

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.

PrevUpHomeNext