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
template<typename RandomAccessIter, typename Unsigned_char_type>
void string_sort(RandomAccessIter first, RandomAccessIter last,
Unsigned_char_type unused);Description
<string_sort>- это быстрый шаблонный алгоритм гибридного радикса / сравнения, который при тестировании имеет тенденцию быть примерно на 50% до 2X быстрее, чем<std::sort>для больших тестов (>=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]](/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> | Итератор указывает на первый элемент. | <last> | Итератор, указывающий на один за пределами конца данных. | <unused> | значение с тем же типом, что и результат оператора [], определяющее тип Unsigned_char_. Реальная стоимость не используется. |
|
Параметры шаблонов: | |
Требуется: | <first>,<last>является допустимым диапазоном. <RandomAccessIter><value_type>является изменчивым. <RandomAccessIter><value_type>являетсяLessThanComparable <RandomAccessIter><value_type>поддерживает<operator>>>, который возвращает целое число сдвинутых справа битов. |
Пост-условия: | Элементы в диапазоне<first>,<last>сортируются в порядке возрастания. |
Броски: | sd:: Исключение Пропагандирует исключения, если какой-либо из элементов сравнения, элемент своп (или ходы), правый сдвиг, вычитание правых сдвинутых элементов, функторы или любые операции на итераторах бросают. |
