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

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, а после нее значение, большее или равное.

А.2.6. Общие функции изменения порядка

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

Базовые версии этих алгоритмов работают "на месте", т.е. они реорганизуют элементы непосредственно исходной последовательности. Три алгоритма изменения порядка предоставляют копирующие версии. Они записывают переупорядоченные значения в получающую последовательность, а не непосредственно в исходную. Для получающей последовательности этим алгоритмам требуются итераторы вывода.

Переупорядочивающие алгоритмы, использующие прямые итераторы

Эти алгоритмы переупорядочивают исходную последовательность. Им необходимы по крайней мере прямые итераторы.

remove(beg, end, val)

remove_if(beg, end, unaryPred)

remove_copy(beg, end, dest, val)

remove_copy_if(beg, end, dest, unaryPred)

"Удаляет" элементы из последовательности, записывая поверх них те элементы, которые должны быть сохранены. Удаляются те элементы, которые равны значению val или те, для которых предикат unaryPred вернул значение true. Возвращает итератор на следующий элемент после последнего удаленного.

unique(beg, end)

unique(beg, end, binaryPred)

unique_copy(beg, end, dest)

unique_copy_if(beg, end, dest, binaryPred)

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

rotate(beg, mid, end)

rotate_copy(beg, mid, end, dest)

"Поворачивает" элементы вокруг элемента, обозначенного итератором mid. Элемент, указанный итератором mid, становится первым элементом, затем идет последовательность от mid+1 до end (но не включая его), далее следует диапазон от beg до mid (но не включая его). Возвращает итератор, обозначающий элемент, который первоначально был в beg.

Переупорядочивающие алгоритмы, использующие двунаправленные итераторы

Поскольку эти алгоритмы обрабатывают исходную последовательность в обратном порядке, им необходимы двунаправленные итераторы.

reverse(beg, end)

reverse_copy(beg, end, dest)

Меняет порядок элементов последовательности на обратный. Алгоритм reverse() возвращает тип void, а алгоритм reverse_copy() возвращает итератор, принимающей последовательности на элемент, который расположен за последним скопированным.

Переупорядочение алгоритмов с помощью итераторов прямого доступа

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

random_shuffle(beg, end)

random_shuffle(beg, end, rand)

shuffle(beg, end, Uniform_rand)

Осуществляет перестановку элементов исходной последовательности в случайном порядке. Перетасовывает элементы в исходной последовательности. Вторая версия получает вызываемый объект, получающий положительное целочисленное значение и возвращающий случайное целое число в диапазоне от нуля до за данного значения с равномерным распределением. Третий аргумент должен отвечать требованиям равномерного генератора случайных чисел (см. раздел 17.4). Все три версии возвращают тип void.

А.2.7. Алгоритмы перестановки

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

Чтобы лучше понять смысл следующей или предыдущей лексикографической перестановки, рассмотрим такую последовательность из трех символов: abc. У этой последовательности есть шесть возможных вариантов перестановки: abc, acb, bac, bca, cab и cba. Эти варианты перестановки перечислены в лексикографическом порядке на основании оператора "меньше". Таким образом, вариант перестановки abc будет первым, поскольку его первый элемент меньше или равен первому элементу любого другого варианта перестановки, а ее второй элемент меньше, чем у любого другого варианта с тем же первым элементом. Точно так же acb — следующий вариант перестановки, поскольку он начинается с символа а, который меньше первого элемента любого из остальных вариантов перестановки. Варианты перестановки, начинающиеся с b, располагаются перед таковыми, начинающимися с c.

Для каждого описанного выше варианта перестановки можно выяснить, какой из них должен располагаться прежде, а какие после него. Например, варианте перестановки bca можно сказать, что предыдущим для нее будет вариант bac, а следующим — cab. Для варианта abc нет предыдущего, а для варианта cba — последующего варианта перестановки.