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

Читать онлайн книгу Введение в стандартную библиотеку шаблонов C++. Описание, примеры использования, учебные задачи - Михаил Абрамян страница 17

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

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

screen_image_45_222_76

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

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

screen_image_45_362_76

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

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

screen_image_45_436_76

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

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

screen_image_46_103_60

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

      Сложность: примерно N*log(middle – first) сравнений.

screen_image_46_198_60

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

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

      Сложность: примерно N1*log(min{N1, N2}) сравнений.

screen_image_46_338_60

      Меняет местами элементы диапазона [first, last) так, чтобы все элементы, удовлетворяющие предикату pred, были расположены СКАЧАТЬ