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

Сложность линейная (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) или (по умолчанию) операция <.