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

Получить обратный итератор r можно из обычного (прямого) итератора p явным приведением типа, например:

Имеется функция-член rbegin(), которая возвращает приведенный к типу обратного итератора итератор end(), и функция-член rend(), возвращающая приведенный к типу обратного итератора итератор begin().

Операции инкремента и декремента прямого и обратного оператора взаимно обратны: r++ перемещает итератор в том же направлении, что и p–, а r– – в том же направлении, что и p++.

Для операции разыменования ^* выполняется следующее базовое соотношение: если r может быть получен из p, то ^*r равно ^*(p – 1).

Функция-член base() обратного итератора возвращает прямой итератор, который можно было бы использовать для получения данного обратного итератора явным приведением типа: если r может быть получен из p, то r.base() == p. Или, иначе говоря, ((reverse_iterator)p).base == p.

Примеры

В следующем примере рассматривается последовательный контейнер cont с исходными элементами 1, 2, 3, 4, 5. Итераторы p2, p3, p4, p5 связаны с элементами 2, 3, 4, 5. Обратные итераторы r2, r3, r4, r5 определены следующим образом (rev – псевдоним типа обратного итератора для cont):

Значения разыменованных итераторов для исходного контейнера:

После выполнения оператора

значения разыменованных итераторов будут следующими («^*» означает, что попытка разыменования приводит к непредсказуемым результатам):

Теперь повторно инициализируем итераторы p4 и r4

и выполним операторы

В результате значения разыменованных итераторов изменятся следующим образом:

Анализ полученных результатов полностью соответствует ранее описанным правилам использования функций insert и erase, а также правилам, связанным с корректностью итераторов. Имеется лишь одно не вполне очевидное обстоятельство, касающееся того, что происходит с обратными итераторами списка, значения которых были связаны с удаляемым элементом (r4) и с элементом, предшествующим удаляемому (r3).

Итератор r3 становится недействительным, что является вполне естественным, так как уничтожается тот элемент, на который указывал итератор r3.base().

В случае итератора r4 ситуация интереснее. Несмотря на то, что значение, которое он возвращал, пропало, сам этот итератор сохранился, поскольку сохранился связанный с ним прямой итератор r4.base() (и, хотя это не отражено в приведенных данных, после выполнения операции удаления значение r4.base() не изменилось). Однако, поскольку после удаления элемента 3 элементом, предшествующим «базовому» элементу, связанному с итератором r4.base(), оказался элемент 2, именно его значение возвращается при разыменовании обратного итератора r4. Таким образом, перед удалением элемента 3 значение итератора r4 было равно 3, а после его удаления значение становится равным предшествующему значению (т. е. 2). При вставке элемента 3 перед элементом 4 базовый элемент для обратного итератора r4 не изменился (он по-прежнему равен p4), но, поскольку теперь перед ним находится элемент 3, именно это значение (3) возвращается разыменованным итератором r4.

1.3. Алгоритмы

Данный раздел содержит описание всех алгоритмов стандартной библиотеки шаблонов, включенных в стандарт C++11. Новые алгоритмы, появившиеся в этом стандарте, помечены текстом C++11. Алгоритм random_shuffle, который объявлен в стандарте C++11 устаревшим, помечен текстом deprecated. Алгоритмы, определенные в заголовочном файле <algorithm>, описаны в п. 1.3.3, алгоритмы, определенные в заголовочном файле <numeric>, – в п. 1.3.4. В каждом пункте алгоритмы располагаются в алфавитном порядке своих имен.

Все алгоритмы определены в пространстве имен std. В таблице 5 алгоритмы сгруппированы в соответствии со способом их применения.

Таблица 5

Алгоритмы STL по категориям

В качестве типов для параметров-итераторов first, last, result, result_last (возможно, дополненных номерами 1 или 2) указываются:

• InIter – итератор чтения (input);

• OutIter – итератор записи (output);

• FwdIter – однонаправленный итератор (forward);

• BidiIter – двунаправленный итератор (bidirectional);

• RandIter – итератор произвольного доступа (random).

В качестве типа значения для входных последовательностей указывается T; если выходная последовательность может иметь тип элементов, отличный от T, то для него используется имя TRes. Итераторы из диапазонов [first, last), [first1, last1), [first2, last2) обозначаются с помощью переменных p, p1, p2 соответственно.

Для типов функциональных объектов в описаниях алгоритмов используются следующие имена:

• UnaryOp – унарная операция (функциональный объект с операцией (), имеющей один параметр типа T; при этом тип возвращаемого значения может отличаться от типа T);

• BinaryOp – бинарная операция (функциональный объект с операцией (), имеющей два параметра, как правило, одинакового типа T; тип возвращаемого значения может отличаться от типа T); если параметры бинарной операции могут иметь различные типы, то об этом явно говорится в описании соответствующего алгоритма;

• Predicate – унарный предикат (унарная операция, возвращающая логическое значение);

• BinaryPredicate – бинарный предикат (бинарная операция с параметрами типа T, возвращающая логическое значение);

• Compare – бинарный предикат, предназначенный для сравнения элементов (аналог операции <);

• Generator – генератор последовательности (функциональный объект с операцией (), не имеющей параметров и возвращающей значение типа TRes);

• RandomGenerator – генератор случайных целых чисел, равномерно распределенных в диапазоне [0, n).

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

Всюду при указании сложности алгоритма под N понимается разность итераторов distance(first, last) (если N имеет индекс, то подразумевается, что итераторы имеют такой же номер, например N₁ = distance(first1, last1)). Если сложность алгоритма является постоянной, т. е. не зависит от размера обрабатываемой последовательности, то она не указывается.

Алгоритмы, описываемые в данном пункте, определены в заголовочном файле <algorithm>.

Находит первую пару соседних элементов из диапазона [first, last), которые равны (или, при наличии предиката pred(^*p, ^*(p + 1)), для которых данный предикат возвращает true). Возвращает итератор, связанный с первым элементом найденной пары, или last, если пара не найдена.

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

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

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

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

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

Использует двоичный поиск для проверки того, содержится ли в диапазоне [first, last) значение value (если значение найдено, то возвращает true, иначе false). Содержимое диапазона должно быть предварительно отсортировано в соответствии с порядком, задаваемым предикатом comp(^*p1, ^*p2) или (по умолчанию) операцией <.

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

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

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

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

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

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

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

Копирует в диапазон, начинающийся с result, n элементов диапазона, начинающегося с first.

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

Возвращает количество элементов в диапазоне [first, last), которые равны значению value.

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

Возвращает количество элементов в диапазоне [first, last), для которых выражение pred(^*p) равно true.

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

Возвращает true, если два диапазона содержат одни и те же элементы в одинаковом порядке. Первый диапазон – [first1, last1), второй начинается с first2 и имеет такую же длину; диапазоны могут перекрываться. Для сравнения используется предикат pred(^*p1, ^*p2) или (по умолчанию) операция ==.

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

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

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

Заполняет выходной диапазон [first, last) значениями value.

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

Заполняет выходной диапазон из n элементов, начиная с first, значениями value.

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

Возвращает итератор, указывающий на первое вхождение элемента value в диапазоне [first, last), или last, если элемент value отсутствует. Для сравнения элементов используется операция ==.

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

Находит последнюю (самую правую) подпоследовательность [first2, last2) в диапазоне [first1, last1). Возвращает итератор, который указывает на начало найденной подпоследовательности, или last1, если подпоследовательность не найдена. Для сравнения элементов используется предикат pred(^*p1, ^*p2) или (по умолчанию) операция ==.

Сложность линейная (не более N₁^*N₂ сравнений).

Находит первое вхождение любого элемента подпоследовательности [first2, last2) в диапазон [first1, last1); возвращает итератор, который указывает на найденный элемент, или last1, если элемент не найден. Для сравнения элементов используется предикат pred(^*p1, ^*p2) или (по умолчанию) операция ==.

Сложность линейная (не более N₁^*N₂ сравнений).

Возвращает итератор, указывающий для диапазона [first, last) на первое вхождение элемента, для которого выражение pred(^*p) возвращает true; если требуемые элементы отсутствуют, то возвращает last.

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

Возвращает итератор, указывающий для диапазона [first, last) на первое вхождение элемента, для которого выражение pred(^*p) возвращает false; если требуемые элементы отсутствуют, то возвращает last.

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

Вызывает функциональный объект f (как f(^*p)) для всех элементов из диапазона [first, last) и возвращает этот же функциональный объект.

Сложность линейная (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^*(N₁ + N₂) – 1 сравнений).

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

Сложность линейная (N + 1 сравнений) или (при нехватке памяти) N^*log N сравнений.

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

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

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

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

Сложность линейная (не более min{N₁, N₂} сравнений).

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

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

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

Сложность линейная (не более 3^*N сравнений).

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

Возвращает позицию первого наибольшего элемента в диапазоне [first, last). В случае пустого диапазона возвращает last. Для сравнения элементов используется предикат comp(^*p1, ^*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₂}) сравнений.

Меняет местами элементы диапазона [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) или (по умолчанию) операция <.

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

Случайным образом изменяет порядок элементов из диапазона [first, last). Для генерации случайных чисел по умолчанию используется встроенный генератор с равномерным распределением; может также использоваться явно заданный генератор rand(n), возвращающий целое случайное число в диапазоне [0, n). В стандарте C++11 алгоритм random_shuffle объявлен устаревшим; вместо него рекомендуется использовать алгоритм shuffle.

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

«Удаляет» из диапазона [first, last) элементы, равные value (для сравнения элементов используется операция ==). Возвращает итератор middle, определяющий конец диапазона [first, middle), содержащего преобразованный набор без удаленных элементов. Относительный порядок оставшихся в диапазоне [first, middle) элементов сохраняется. В результате выполнения алгоритма значения элементов в диапазоне [middle, last) становятся неопределенными.

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

Копирует в диапазон, начинающийся с result, все элементы диапазона [first, last), кроме элементов, равных value (для сравнения элементов используется операция ==). Возвращает позицию за последним скопированным элементом в полученном диапазоне. Относительный порядок элементов в полученном диапазоне сохраняется. Исходный и результирующий диапазоны не должны перекрываться.

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

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

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

«Удаляет» из диапазона [first, last) элементы, для которых pred возвращает true. Возвращает итератор middle, определяющий конец диапазона [first, middle), содержащего преобразованный набор без удаленных элементов. Относительный порядок оставшихся в диапазоне [first, middle) элементов сохраняется. В результате выполнения алгоритма значения элементов в диапазоне [middle, last) становятся неопределенными.

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

Заменяет в диапазоне [first, last) все вхождения значения old_value на new_value.

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

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

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

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

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

Заменяет в диапазоне [first, last) все элементы, для которых pred возвращает true, на new_value.

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

Переставляет элементы диапазона [first, last) в обратном порядке.

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

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

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

Циклически сдвигает элементы диапазона [first, last) так, что элементы из диапазона [middle, last) оказываются в начале новой последовательности (элементы из диапазона [first, middle) передвигаются в конец последовательности).

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

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

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

Находит первую (самую левую) подпоследовательность [first2, last2) в диапазоне [first1, last1). Возвращает итератор, который указывает на начало найденной подпоследовательности, или last1, если подпоследовательность не найдена. Для сравнения элементов используется предикат pred(^*p1, ^*p2) или (по умолчанию) операция ==.

Сложность линейная (не более N₁^*N₂ сравнений).

Находит первую (самую левую) подпоследовательность из count соседних одинаковых значений value в диапазоне [first, last). Возвращает итератор, который указывает на начало найденной подпоследовательности, или last, если подпоследовательность не найдена. Для сравнения элементов используется предикат pred(^*p1, ^*p2) или (по умолчанию) операция == (фактически второй параметр в предикате всегда полагается равным value).