Язык программирования C++. Пятое издание

Копирует или перемещает элементы из исходного диапазона в заданный. В отличие от других алгоритмов, dest — итератор после конца для выходной последовательности (т.е. последовательность назначения закончится непосредственно перед dest). Последний элемент в исходном диапазоне копируется или перемещается в последний элемент назначения, затем копируется (перемещается) предпоследний элемент и т.д. У элементов в последовательности назначения тот же порядок, что и в исходном диапазоне. Если диапазон пуст, возвращается итератор dest, в противном случае возвращается итератор на элемент, который был скопирован или перемещен из *beg.

inplace_merge(beg, mid, end)

inplace_merge(beg, mid, end, comp)

Объединяет две отсортированные внутренние последовательности из той же последовательности в единую, упорядоченную последовательность. Внутренние последовательности от beg до mid и от mid до end объединяются и записываются назад в первоначальную последовательность. Первая версия использует для сравнения элементов оператор <, а вторая версия использует заданную операцию сравнения. Возвращают void.

А.2.5. Алгоритмы сортировки и разделения

Алгоритмы сортировка и разделения предоставляют различные стратегии упорядочивания элементов последовательности.

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

Алгоритмы разделения

Алгоритмы разделения делят элементы исходного диапазона на две группы. Первая группа состоит из элементов удовлетворяющих определенному предикату, а вторая — нет. Например, элементы последовательности можно разделить на основании четности их значений или на основании того, начинается ли слово с заглавной буквы, и так далее. Этим алгоритмам требуются двунаправленные итераторы.

is_partitioned(beg, end, unaryPred)

Возвращает значение true, если все элементы, удовлетворяющие предикату unaryPred, предшествуют тем, для которых предикат unaryPred возвращает значение false. Если последовательность пуста, также возвращается значение true.

partition_copy(beg, end, dest1, dest2, unaryPred)

Копирует в dest1 элементы, для которых истин предикат unaryPred, а остальные копирует в dest2. Возвращает пару (см. раздел 11.2.3) итераторов. Член first пары обозначает конец скопированных в dest1 элементов, а член second обозначает конец элементов, скопированных в dest2. Исходная последовательность не может налагаться ни на одну из результирующих последовательностей.

partition_point(beg, end, unaryPred)

Для разделения исходной последовательности используется предикат unaryPred. Возвращает итератор на элемент за последним, удовлетворяющим предикату unaryPred. Если возвращен итератор не end, то предикат unaryPred должен возвращать значение false для возвращенного итератора и для всех элементов, следующих за ним.

stable_partition(beg, end, unaryPred)

partition(beg, end, unaryPred)

Для разделения исходной последовательности используется предикат unaryPred. Элементы, для которых истин предикат unaryPred, помещаются в начало последовательности, а остальные в конец. Возвращает итератор на элемент за последним, удовлетворяющим предикату unaryPred, или итератор beg, если таких элементов нет.

Алгоритмы сортировки

Этим алгоритмам требуются итераторы прямого доступа. Каждый из алгоритмов сортировки предоставляется в двух перегруженных версиях. В одной из них для сравнения элементов используется оператор < типа элемента, а во второй предусмотрен дополнительный параметр для функции сравнения (см. раздел 11.2.2). Алгоритм partial_sort_copy() возвращает итератор получателя, а остальные возвращают void.

Алгоритмы partial_sort() и nth_element() выполняют частичную сортировку последовательности. Их используют в случае, когда в результате сортировки всей последовательности могут возникнуть проблемы. Поскольку эти операции являются менее трудоемкими, они выполняются быстрее, чем сортировка всего исходного диапазона.

sort(beg, end)

stable_sort(beg, end)

sort(beg, end, comp)

stable_sort(beg, end, comp)

Сортирует весь диапазон.

is_sorted(beg, end)

is_sorted(beg, end, comp)

is_sorted_until(beg, end)

is_sorted_until(beg, end, comp)