Function template reverse_string_sort
boost::sort::spreadsort::reverse_string_sort — Reverse String sort algorithm using random access iterators.
Synopsis
template<typename RandomAccessIter, typename Get_char, typename Get_length,
typename Compare>
void reverse_string_sort(RandomAccessIter first, RandomAccessIter last,
Get_char getchar, Get_length length, Compare comp);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 (за исключением строк, где это журнал размера символа).
Параметры: | comp
| Бинарный функтор, который возвращает, должен ли первый элемент, переданный ему, идти перед вторым по порядку. | <first> | Итератор указывает на первый элемент. | <getchar> | Функтор скобки эквивалентен<operator>[], принимая число, соответствующее смещение символа. | <last> | Итератор, указывающий на один за пределами конца данных. | <length> | Функтор для получения длины строки в символах. |
|
Требуется: | <first>,<last>является допустимым диапазоном. <RandomAccessIter><value_type>является изменчивым. <RandomAccessIter><value_type>Менее сравним |
Постусловия: | Элементы в диапазоне<first>,<last>сортируются в порядке возрастания. |
Возвращение: | <void> |
Броски: | sd:: Исключение Пропагандирует исключения, если какой-либо из элементов сравнения, элемент своп (или ходы), правый сдвиг, вычитание правых сдвинутых элементов, функторы или любые операции на итераторах бросают. |
