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

Переупорядочивает содержимое диапазона [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₂}) сравнений.

Меняет местами элементы диапазона [first, last) так, чтобы все элементы, удовлетворяющие предикату pred, были расположены перед теми, которые ему не удовлетворяют. Относительный порядок следования элементов не сохраняется. Алгоритм возвращает итератор, указывающий на первый элемент, для которого pred возвращает false (или итератор last, если таких элементов нет).

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

Копирует элементы из диапазона [first, last) в два выходных диапазона: элементы, удовлетворяющие предикату pred, копируются в первый диапазон (начинающийся с result1), а остальные элементы – во второй диапазон (начинающийся с result2). Исходный диапазон не должен перекрываться с выходными диапазонами. Возвращает пару итераторов, определяющих позиции за концами первого и второго полученного диапазона (в указанном порядке).

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

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

Сложность логарифмическая (не более log N вызовов pred).

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

Сложность логарифмическая (не более 2^*log N сравнений).

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

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

При условии, что диапазон [first, last – 1) является кучей (см. алгоритм make_heap), добавляет в эту кучу элемент, расположенный в позиции last – 1, формируя тем самым кучу в диапазоне [first, last). Для сравнения элементов используется предикат comp(^*p1, ^*p2) или (по умолчанию) операция <.