Function template string_sort
boost::sort::spreadsort::string_sort — String sort algorithm using random access iterators, wraps using default of unsigned char.
Synopsis
template<typename RandomAccessIter, typename Get_char, typename Get_length>
void string_sort(RandomAccessIter first, RandomAccessIter last,
Get_char getchar, Get_length length);Description
(Все варианты возвращаются к<std::sort>, если размер данных слишком мал,<<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]](/img/warning.png) | Warning |
|---|
Бросок исключения может привести к потере данных. Это также будет бросать, если бросит небольшой вектор размера, и в этом случае не будет потери данных. Недействительные аргументы вызывают неопределенное поведение. |
![[Note]](/img/note.png) | Note |
|---|
<spreadsort>Функция обеспечивает обертку, которая называет самый быстрый алгоритм сортировки, доступный для типа данных, что позволяет ускорить общее программирование. |
Меньшая изO(N*log(N))сравнения иO(N*log(K/S + S))Наихудший случай, когда:
N<last>-<first>,
K - журнал диапазона в битах (32 для 32-битных целых чисел с использованием их полного диапазона),
S - постоянная, называемая max_splits, по умолчанию 11 (за исключением строк, где это журнал размера символа).
Параметры: | <first> | Итератор указывает на первый элемент. | <getchar> | Функтор скобки, эквивалентный<operator>[], принимая число, соответствующее зачету символа. | <last> | Итератор, указывающий на один за пределами конца данных. | <length> | Функтор для получения длины строки в символах. |
|
Требуется: | [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>сортируются в порядке возрастания. |
Возвращение: | <void> |
Броски: | sd:: Исключение Пропагандирует исключения, если какой-либо из элементов сравнения, элемент своп (или ходы), правый сдвиг, вычитание правых сдвинутых элементов, функторы или любые операции на итераторах бросают. |
