Function template integer_sort
boost::sort::spreadsort::integer_sort — 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).
Synopsis
template<typename RandomAccessIter>
void integer_sort(RandomAccessIter first, RandomAccessIter last);
Description
<integer_sort>- это быстрый шаблонный алгоритм гибридного радикса / сравнения, который при тестировании имеет тенденцию быть примерно на 50% до 2X быстрее, чем<std::sort>для больших тестов (>=100kB).
Наихудшая производительностьO(N * (lg(range)/s + s)), так что<integer_sort>асимптотически быстрее, чем чистые алгоритмы на основе сравнения.<s>это<max_splits>, который по умолчанию 11, поэтому его наихудший случай с настройками по умолчанию для 32-разрядных целых чисел составляетO(N*(32/11)медленные итерации на основе радикса, быстрые итерации на основе сравнения.
Предусмотрены некоторые графики исполнения runtime vs. n и log(range):
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> | Итератор указывает на первый элемент. | <last> | Итератор, указывающий на один за пределами конца данных. |
|
Требуется: | <first>,<last>является допустимым диапазоном. <RandomAccessIter><value_type>является изменчивым. <RandomAccessIter><value_type>являетсяLessThanComparable <RandomAccessIter><value_type>поддерживает<operator>>>, который возвращает целое число правого сдвига, заданное число битов. |
Постусловия: | Элементы в диапазоне<first>,<last>сортируются в порядке возрастания. |
Броски: | sd:: Исключение Пропагандирует исключения, если какой-либо из элементов сравнения, элемент своп (или ходы), правый сдвиг, вычитание правых сдвинутых элементов, функторы или любые операции на итераторах бросают. |
