Введение в стандартную библиотеку шаблонов C++. Описание, примеры использования, учебные задачи

p2) или (по умолчанию) операция <.

Сложность линейная (max{N – 1, 0} сравнений).

Выполняет слияние двух предварительно отсортированных диапазонов [first1, last1) и [first2, last2) и копирование результата в последовательность, начиная с result (в выходной последовательности должно быть достаточно места для полученного набора данных). Возвращает выходной итератор, указывающий на позицию за концом добавленного набора данных. Выходной диапазон не должен накладываться ни на один из исходных диапазонов. Слияние является устойчивым; кроме того, в полученном диапазоне равные элементы из первого диапазона будут располагаться перед равными им элементами из второго диапазона. Для сравнения элементов используется предикат comp(

p1,

p2) или (по умолчанию) операция <.

Сложность линейная (не более N

+ N

– 1 сравнений).

Возвращает меньшее из значений a и b (при их равенстве возвращается a). Для сравнения значений используется предикат comp(a, b) или (по умолчанию) операция <.

Возвращает позицию первого наименьшего элемента в диапазоне [first, last). В случае пустого диапазона возвращает last. Для сравнения элементов используется предикат comp(

p1,

p2) или (по умолчанию) операция <.

Сложность линейная (max{N – 1, 0} сравнений).

Возвращает пару, содержащую меньшее и большее из значений a и b (при их равенстве возвращается пара (a, b)). Для сравнения значений используется предикат comp(a, b) или (по умолчанию) операция <.

Возвращает пару, содержащую позиции первого наименьшего и последнего наибольшего элемента в диапазоне [first, last). В случае пустого диапазона возвращает пару (last, last). Для сравнения элементов используется предикат comp(

p1,

p2) или (по умолчанию) операция <.

Сложность линейная (не более max{floor(3/2

(N – 1)), 0} сравнений).

Выполняет попарное сравнение элементов из диапазона [first1, last1) и диапазона, начинающегося с first2 и имеющего длину, не меньшую, чем длина первого диапазона. Возвращает первую пару различных элементов (или, если все элементы первого диапазона совпадают с соответствующими элементами второго диапазона, пару из итератора last1 и соответствующего итератора для второго диапазона). Для сравнения элементов используется предикат pred(

p1,

p2) или (по умолчанию) операция ==.

Сложность линейная (не более N

сравнений).

Перемещает элементы из [first, last) в диапазон, начинающийся с result, и возвращает позицию за последним перемещенным элементом в полученном диапазоне. Итератор result не может находиться в исходном диапазоне [first, last). После выполнения этого алгоритма диапазон [first, last) будет попрежнему содержать элементы того же типа, но их значения могут отличаться от исходных.

Сложность линейная (N присваиваний).

Выполняет те же действия, что и move, но перебирает исходные данные в обратном порядке: от элемента, предшествующего last, до first. Итератор result_last должен указывать на элемент, следующий за концом формируемой выходной последовательности; возвращаемое значение – это итератор, указывающий на первый элемент выходной последовательности. Итератор result_last не может находиться в диапазоне (first, last] (обратите внимание на границы этого диапазона).

Сложность линейная (N присваиваний).

Переупорядочивает содержимое диапазона [first, last), создавая следующую перестановку из набора лексикографически упорядоченных перестановок элементов данного диапазона. Возвращает true, если перестановка была создана успешно, или false, если исходный диапазон представлял собой последнюю (в лексикографическом порядке) перестановку; в этом последнем случае генерируется первая в лексикографическом порядке перестановка (в которой все элементы расположены в порядке возрастания). Для сравнения элементов используется предикат comp(

p1,

p2) или (по умолчанию) операция <.

Сложность линейная (не более N/2 перемещений).

Возвращает true, если ни один из элементов диапазона [first, last) не удовлетворяет предикату pred. В случае пустого диапазона также возвращается true.

Сложность линейная (не более N вызовов pred).

Переупорядочивает диапазон [first, last) таким образом, чтобы в позиции nth размещался элемент, который стоял бы на этом месте в случае, если бы весь диапазон был отсортирован. Кроме того, в результате выполнения данного алгоритма все элементы в диапазоне [first, nth) не будут превосходить элементы из диапазона [nth, last). Алгоритм не является устойчивым: если имеется несколько элементов, которые при сортировке могли бы оказаться на позиции nth, то нельзя сказать, какой из них будет перемещен на эту позицию. Для сравнения элементов используется предикат comp(

p1,

p2) или (по умолчанию) операция <.

Сложность в среднем линейная (около N сравнений).

Частично сортирует элементы диапазона [first, last), размещая отсортированные элементы в диапазоне [first, middle). Оставшиеся элементы никак не упорядочиваются. Алгоритм не является устойчивым. Для сравнения элементов используется предикат comp(

p1,

p2) или (по умолчанию) операция <.

Сложность: примерно N

log(middle – first) сравнений.

Частично сортирует элементы из диапазона [first1, last1) и копирует отсортированную часть в диапазон [first2, last2). Размер сортируемой части определяется размером второго диапазона: если он меньше первого, то сортируется часть первого диапазона, если он больше или равен размеру первого диапазона, то сортируется весь первый диапазон.

Возвращается итератор второго диапазона, указывающий на позицию за концом отсортированного набора данных, добавленного из первого диапазона. Для сравнения элементов используется предикат comp(

p1,

p2) или (по умолчанию) операция <.

Сложность: примерно N

log(min{N

, N