Boost.Sort
|
Functions | |
template<class Data_type , class Cast_type > | |
Cast_type | float_mem_cast (const Data_type &data) |
Casts a float to the specified integer type. More... | |
template<class RandomAccessIter > | |
void | float_sort (RandomAccessIter first, RandomAccessIter last) |
float_sort with casting to the appropriate size. More... | |
template<class RandomAccessIter , class Right_shift > | |
void | float_sort (RandomAccessIter first, RandomAccessIter last, Right_shift rshift) |
Floating-point sort algorithm using random access iterators with just right-shift functor. More... | |
template<class RandomAccessIter , class Right_shift , class Compare > | |
void | float_sort (RandomAccessIter first, RandomAccessIter last, Right_shift rshift, Compare comp) |
Float sort algorithm using random access iterators with both right-shift and user-defined comparison operator. More... | |
template<class RandomAccessIter > | |
void | integer_sort (RandomAccessIter first, RandomAccessIter last) |
Integer sort algorithm using random access iterators. (All variants fall back to std::sort if the data size is too small, < detail::min_sort_size ). More... | |
template<class RandomAccessIter , class Right_shift , class Compare > | |
void | integer_sort (RandomAccessIter first, RandomAccessIter last, Right_shift shift, Compare comp) |
Integer sort algorithm using random access iterators with both right-shift and user-defined comparison operator. (All variants fall back to std::sort if the data size is too small, < detail::min_sort_size ). More... | |
template<class RandomAccessIter , class Right_shift > | |
void | integer_sort (RandomAccessIter first, RandomAccessIter last, Right_shift shift) |
Integer sort algorithm using random access iterators with just right-shift functor. (All variants fall back to std::sort if the data size is too small, < detail::min_sort_size ). More... | |
template<class RandomAccessIter > | |
boost::enable_if_c< std::numeric_limits< typename std::iterator_traits< RandomAccessIter >::value_type >::is_integer, void >::type | spreadsort (RandomAccessIter first, RandomAccessIter last) |
Generic spreadsort variant detecting integer-type elements so call to integer_sort . More... | |
template<class RandomAccessIter > | |
boost::enable_if_c< !std::numeric_limits< typename std::iterator_traits< RandomAccessIter >::value_type >::is_integer &&std::numeric_limits< typename std::iterator_traits< RandomAccessIter >::value_type >::is_iec559, void >::type | spreadsort (RandomAccessIter first, RandomAccessIter last) |
Generic spreadsort variant detecting float element type so call to float_sort . More... | |
template<class RandomAccessIter > | |
boost::enable_if_c< is_same< typename std::iterator_traits< RandomAccessIter >::value_type, typename std::string >::value||is_same< typename std::iterator_traits< RandomAccessIter >::value_type, typename std::wstring >::value, void >::type | spreadsort (RandomAccessIter first, RandomAccessIter last) |
Generic spreadsort variant detecting string element type so call to string_sort for std::strings and std::wstrings . More... | |
template<class RandomAccessIter , class Unsigned_char_type > | |
void | string_sort (RandomAccessIter first, RandomAccessIter last, Unsigned_char_type unused) |
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 ). More... | |
template<class RandomAccessIter > | |
void | string_sort (RandomAccessIter first, RandomAccessIter last) |
String sort algorithm using random access iterators, wraps using default of unsigned char. (All variants fall back to std::sort if the data size is too small, < detail::min_sort_size ). More... | |
template<class RandomAccessIter , class Compare , class Unsigned_char_type > | |
void | reverse_string_sort (RandomAccessIter first, RandomAccessIter last, Compare comp, Unsigned_char_type unused) |
String sort algorithm using random access iterators, allowing character-type overloads. More... | |
template<class RandomAccessIter , class Compare > | |
void | reverse_string_sort (RandomAccessIter first, RandomAccessIter last, Compare comp) |
String sort algorithm using random access iterators, wraps using default of unsigned char. More... | |
template<class RandomAccessIter , class Get_char , class Get_length > | |
void | string_sort (RandomAccessIter first, RandomAccessIter last, Get_char get_character, Get_length length) |
String sort algorithm using random access iterators, wraps using default of unsigned char. More... | |
template<class RandomAccessIter , class Get_char , class Get_length , class Compare > | |
void | string_sort (RandomAccessIter first, RandomAccessIter last, Get_char get_character, Get_length length, Compare comp) |
String sort algorithm using random access iterators, wraps using default of unsigned char. More... | |
template<class RandomAccessIter , class Get_char , class Get_length , class Compare > | |
void | reverse_string_sort (RandomAccessIter first, RandomAccessIter last, Get_char get_character, Get_length length, Compare comp) |
Reverse String sort algorithm using random access iterators. More... | |
Namespace for spreadsort sort variants for different data types.
|
inline |
Casts a float to the specified integer type.
Data_type | Floating-point IEEE 754/IEC559 type. |
Cast_type | Integer type (same size) to which to cast. |
|
inline |
float_sort
with casting to the appropriate size.
RandomAccessIter | Random access iterator |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
Some performance plots of runtime vs. n and log(range) are provided:
windows_float_sort
osx_float_sort
|
inline |
Floating-point sort algorithm using random access iterators with just right-shift functor.
RandomAccessIter | Random access iterator |
Right_shift | Functor for right-shift by parameter shift bits. |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
[in] | rshift | Number of bits to right-shift (using functor). |
|
inline |
Float sort algorithm using random access iterators with both right-shift and user-defined comparison operator.
RandomAccessIter | Random access iterator |
Right_shift | functor for right-shift by parameter shift bits. |
Comp | To provide operator< for user-defined comparison. |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
[in] | rshift | Number of bits to right-shift (using functor). |
[in] | comp | comparison functor. |
|
inline |
Integer sort algorithm using random access iterators. (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
RandomAccessIter | Random access iterator |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
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. 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. |
spreadsort
function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.last
- first
,
|
inline |
Integer sort algorithm using random access iterators with both right-shift and user-defined comparison operator. (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
RandomAccessIter | Random access iterator |
Right_shift | functor for right-shift by parameter shift bits. |
Comp | To provide operator< for user-defined comparison. |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
[in] | shift | Number of bits to right-shift (using functor). |
[in] | comp | comparison functor. |
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. first
, last
) are sorted in ascending order.void
.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. |
spreadsort
function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.last
- first
,
|
inline |
Integer sort algorithm using random access iterators with just right-shift functor. (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).
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).RandomAccessIter | Random access iterator |
Right_shift | functor for right-shift by parameter shift bits. |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
[in] | shift | Number of bits to right-shift (using functor). |
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. 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. |
spreadsort
function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.last
- first
,
|
inline |
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).
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
RandomAccessIter | Random access iterator |
Comp | To provide operator< for user-defined comparison. |
Unsigned_char_type | Unsigned character type used for string. |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
[in] | comp | comparison functor. |
[in] | unused | Unused ??? |
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. first
, last
) are sorted in ascending order.void
.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. |
spreadsort
function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.last
- first
,
|
inline |
String sort algorithm using random access iterators, wraps using default of unsigned
char.
(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
RandomAccessIter | Random access iterator |
Comp | To provide operator< for user-defined comparison. |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
[in] | comp | Comparison functor. |
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. first
, last
) are sorted in ascending order.void
.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. |
spreadsort
function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.last
- first
,
|
inline |
Reverse String sort algorithm using random access iterators.
(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
RandomAccessIter | Random access iterator |
Get_char | ???. |
Get_length | ??? TODO |
Comp | To provide operator< for user-defined comparison. |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
[in] | comp | comparison functor. |
[in] | get_character | ??? |
[in] | length | ??? |
first
, last
) is a valid range. RandomAccessIter
value_type
is mutable. RandomAccessIter
value_type
is LessThanComparable first
, last
) are sorted in ascending order.void
.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. |
spreadsort
function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.last
- first
,
|
inline |
Generic spreadsort
variant detecting integer-type elements so call to integer_sort
.
If the data type provided is an integer, integer_sort
is used.
integer_sort
, float_sort
and string_sort
directly, as spreadsort
won't accept types that don't have the appropriate type_traits
. RandomAccessIter | Random access iterator |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
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. first
, last
) are sorted in ascending order.
|
inline |
Generic spreadsort
variant detecting float element type so call to float_sort
.
If the data type provided is a float or castable-float, float_sort
is used.
integer_sort
, float_sort
and string_sort
directly, as spreadsort
won't accept types that don't have the appropriate type_traits
.RandomAccessIter | Random access iterator |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
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. first
, last
) are sorted in ascending order.
|
inline |
Generic spreadsort
variant detecting string element type so call to string_sort
for std::strings
and std::wstrings
.
If the data type provided is a string or wstring, string_sort
is used.
integer_sort
, float_sort
and string_sort
directly, as spreadsort
won't accept types that don't have the appropriate type_traits
.RandomAccessIter | Random access iterator |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
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. first
, last
) are sorted in ascending order.
|
inline |
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
).
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).
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).RandomAccessIter | Random access iterator |
Unsigned_char_type | Unsigned character type used for string. |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
[in] | unused | Unused ??? |
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. 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. |
spreadsort
function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.last
- first
,
|
inline |
String sort algorithm using random access iterators, wraps using default of unsigned char. (All variants fall back to std::sort
if the data size is too small, < detail::min_sort_size
).
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
RandomAccessIter | Random access iterator |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
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. 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. |
spreadsort
function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.last
- first
,
|
inline |
String sort algorithm using random access iterators, wraps using default of unsigned
char.
(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
RandomAccessIter | Random access iterator |
Get_char | Bracket functor equivalent to operator [], taking a number corresponding to the character offset.. |
Get_length | Functor to get the length of the string in characters. TODO Check this and below and other places!!! |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
[in] | get_character | Number corresponding to the character offset from bracket functor equivalent to operator []. |
[in] | length | Functor to get the length of the string in characters. |
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. first
, last
) are sorted in ascending order.void
.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. |
spreadsort
function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.last
- first
,
|
inline |
String sort algorithm using random access iterators, wraps using default of unsigned
char.
(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
RandomAccessIter | Random access iterator |
Get_char | ???. |
Get_length | ??? TODO |
Comp | To provide operator< for user-defined comparison. |
[in] | first | Iterator pointer to first element. |
[in] | last | Iterator pointing to one beyond the end of data. |
[in] | comp | comparison functor. |
[in] | get_character | ??? |
[in] | length | ??? |
first
, last
) is a valid range. RandomAccessIter
value_type
is mutable. RandomAccessIter
value_type
is LessThanComparable first
, last
) are sorted in ascending order.void
.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. |
spreadsort
function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.last
- first
,