Сортировка — это очень часто выполняющаяся операция, и есть два способа отсортировать последовательность. Можно обеспечить хранение элементов в определенном порядке с помощью ассоциативного контейнера, но при этом длительность операции вставки будет иметь логарифмическую зависимость от размера последовательности. Либо можно сортировать элементы только по мере надобности с помощью

, имеющей несколько опций.

Стандартный алгоритм

делает именно то, что от него ожидается: он сортирует элементы диапазона в восходящем порядке с помощью . Он объявлен вот так.

Как и в большинстве других алгоритмов, если

не удовлетворяет вашим требованиям, можно указать собственный оператор сравнения. В среднем случае сложность имеет зависимость n log n. В худшем случае она может быть квадратичной.

Если требуется, чтобы одинаковые элементы сохранили свой первоначальный порядок, используйте

. Он имеет такую же сигнатуру, но гарантирует, что порядок эквивалентных элементов изменен не будет. Его сложность при наличии достаточного объема памяти в худшем случае составляет n log n. Если памяти недостаточно, то сложность может оказаться равной n(log n)².

Однако

работает не для всех контейнеров. Он требует итераторов произвольного доступа, так что при использовании контейнера, не предоставляющего таких итераторов, он неприменим. Итераторы произвольного доступа предоставляют стандартные последовательные контейнеры , и / (которые не являются контейнерами, но удовлетворяют большинству требований к ним), — это единственный, который такого итератора не предоставляет. Если требуется отсортировать список, используйте . Например, в примере 7.6 вы, вероятно, заметили, что не принимает никаких аргументов.

Это отличает его от

, с помощью которого можно отсортировать только часть последовательности. Если требуется отсортировать часть последовательности, то не следует использовать .

Концепция сортировки очень проста, но есть несколько вариаций на тему ее реализации в стандартной библиотеке. Следующий перечень описывает эти вариации.

Принимает три итератора произвольного доступа —

, и — и (необязательно) функтор сравнения. Он имеет два постусловия: элементы диапазона (, ) будут меньше, чем элементы диапазона (, ), и диапазон (, ) будет отсортирован с помощью или указанного функтора сравнения. Другими словами, он сортирует только первые n элементов.

Делает то же, что и

, но помещает результаты в выходной диапазон. Он берет первые n элементов из исходного диапазона и в соответствующем порядке копирует их в результирующий диапазон. Если результирующий диапазон (n) короче, чем исходный диапазон (m), то в результирующий диапазон копируется только n элементов.

Принимает три итератора произвольного доступа —

, и — и необязательный функтор сравнения. Он помешает элемент, на который ссылается , в то место, где он находился бы, если бы весь диапазон был отсортирован. Следовательно, все элементы диапазона (, ) будут меньше, чем элемент в позиции (те, что находятся в диапазоне (, ) не сортируются, но больше, чем те, что предшествуют ). Этот алгоритм следует использовать тогда, когда требуется отсортировать только один или несколько элементов диапазона и избежать затрат на сортировку всего диапазона.

Также можно разделить элементы диапазона в соответствии с каким-либо критерием (функтором), и это является предметом обсуждения рецепта 7.7.

Рецепт 7.7.

Имеется диапазон элементов, которые требуется каким-либо образом разделить на группы. Например, необходимо переместить в начало диапазона все элементы, которые меньше определенного значения.

Для перемещения элементов используйте стандартный алгоритм

с предикатом-функтором. См. пример 7.7.

Пример 7.7. Разделение диапазона