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

PrevUpHomeNext

Function template string_sort

boost::sort::spreadsort::string_sort — String sort algorithm using random access iterators, allowing character-type overloads.
(All variants fall back to std::sort if the data size is too small, < detail::min_sort_size).

Synopsis

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


template<typename RandomAccessIter, typename Unsigned_char_type> 
  void string_sort(RandomAccessIter first, RandomAccessIter last, 
                   Unsigned_char_type unused);

Description

string_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_string_sort
osx_string_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:

first

Iterator pointer to first element.

last

Iterator pointing to one beyond the end of data.

unused

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

Template Parameters:

RandomAccessIter

Random access iterator

Unsigned_char_type

Unsigned character type used for string.

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.

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