Введение в стандартную библиотеку шаблонов C++. Описание, примеры использования, учебные задачи
Шрифт:
Возвращает итератор, указывающий для диапазона [first, last) на первое вхождение элемента, для которого выражение pred(*p) возвращает false; если требуемые элементы отсутствуют, то возвращает last.
Сложность линейная (не более N вызовов pred).
Вызывает функциональный объект f (как f(*p))
Сложность линейная (N вызовов f).
Заполняет диапазон [first, last), последовательно присваивая элементам диапазона результат вызова функционального объекта gen (как gen).
Сложность линейная (N вызовов gen).
Заполняет последовательность, начинающуюся с позиции first, n элементами, полученными в результате вызова функционального объекта gen (как gen).
Сложность линейная (n вызовов gen).
Возвращает true, если все элементы предварительно отсортированной последовательности [first2, last2) содержатся в предварительно отсортированной последовательности [first1, last1), и false в противном случае (фактически ищется вхождение подпоследовательности [first2, last2) в диапазон [first1, last1)). Для сравнения элементов используется предикат comp(*p1, *p2) или (по умолчанию) операция <.
Сложность линейная (не более 2*(N1 + N2) – 1 сравнений).
Выполняет слияние двух предварительно отсортированных частей [first, middle) и [middle, last) последовательности на месте, в результате чего создается единый отсортированный диапазон [first, last). Слияние является устойчивым; кроме того, в полученном диапазоне равные элементы из первого диапазона будут располагаться перед равными им элементами из второго диапазона. Для сравнения элементов используется предикат comp(*p1, *p2) или (по умолчанию) операция <.
Сложность линейная (N + 1 сравнений) или (при нехватке памяти) N*log N сравнений.
Возвращает true, если диапазон [first, last) представляет собой кучу (см. алгоритм make_heap). Для сравнения элементов используется предикат comp(*p1, *p2) или (по умолчанию) операция <.
Сложность линейная (не более N сравнений).
Определяет
Сложность линейная (не более N сравнений).
Возвращает true, если в диапазоне [first, last) все элементы, удовлетворяющие предикату pred, расположены перед всеми элементами, которые предикату не удовлетворяют. В случае пустого диапазона также возвращается true.
Сложность линейная (не более N вызовов pred).
Возвращает true, если диапазон [first1, last1) представляет собой перестановку элементов диапазона, который начинается с first2 и имеет такую же длину. Для сравнения используется предикат pred(*p1, *p2) или (по умолчанию) операция ==.
Сложность: не более N*N вызовов pred (ровно N вызовов в случае, если элементы первого диапазона совпадают с соответствующими элементами второго диапазона).
Возвращает true, если диапазон [first, last) представляет собой отсортированную последовательность. Для сравнения элементов используется предикат comp(*p1, *p2) или (по умолчанию) операция <.
Сложность линейная (не более N сравнений).
Определяет наибольший диапазон в пределах исходного диапазона [first, last), который начинается с first и представляет собой отсортированную последовательность. Возвращает позицию за концом найденного диапазона. Для сравнения элементов используется предикат comp(*p1, *p2) или (по умолчанию) операция <.
Сложность линейная (не более N сравнений).
Меняет местами значения, на которые указывают итераторы a и b.
Возвращает true, если последовательность [first1, last1) «меньше» (в лексикографическом смысле), чем последовательность [first2, last2), и false в противном случае (в частности, если последовательности равны, то возвращается false, а если первая последовательность является собственным префиксом второй, то возвращается true). Для сравнения элементов используется предикат comp(*p1, *p2) или (по умолчанию) операция <.