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

inplace_merge(beg, mid, end)

inplace_merge(beg, mid, end, comp)

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

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

Каждый алгоритм сортировки и разделения поддерживает стабильные и нестабильные версии (см. раздел 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)

Алгоритм is sorted()возвращает логическое значение, указывающее, сортируется ли вся исходная последовательность. Алгоритм is_sorted_until()находит самую длинную изначально отсортированную часть в исходной последовательности и возвращает итератор на позицию сразу после ее конца.

partial_sort(beg, mid, end)

partial_sort(beg, mid, end, comp)

Сортирует набор элементов, количество которых равно mid-beg. То есть если mid-begравно 42, эта функция помещает элементы с самыми низкими значениями, в отсортированном порядке, в первые 42 позиции последовательности. После завершения работы алгоритма partial_sort()окажутся отсортированы элементы в диапазоне от begи далее, но не включая mid. Ни один из элементов в отсортированном диапазоне не больше, чем любой из элементов в диапазоне после mid. Порядок неотсортированных элементов не определен.

partial_sort_copy(beg, end, destBeg, destEnd)

partial_sort_copy(beg, end, destBeg, destEnd, comp)

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

Алгоритм возвращает итератор в получающем диапазоне, указывающий на следующий элемент после последнего отсортированного. Если получающая последовательность меньше исходного диапазона или равна ему по размеру, будет возвращен итератор destEnd.

nth_element(beg, nth, end)

nth_element(beg, nth, end, comp)

Аргумент nthдолжен быть итератором, указывающим на элемент в исходной последовательности. Обозначенный этим итератором элемент после выполнения алгоритма nth_elementимеет значение, которое находилось бы там после сортировки всей последовательности. Кроме того, элементы контейнера вокруг позиции nthтакже отсортированы: перед ней располагается значение меньше или равное значению в позиции nth, а после нее значение, большее или равное.

Некоторые алгоритмы переупорядочивают элементы исходной последовательности. Первые два, remove()и unique(), переупорядочивают последовательность так, чтобы элементы в первой части удовлетворяли некоему критерию. Они возвращают итератор, отмечающий конец этой подпоследовательности. Другие, например reverse(), rotate()и random_shuffle(), реорганизуют всю последовательность.