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

Анализ полученных результатов полностью соответствует ранее описанным правилам использования функций 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. Алгоритмы

1.3.1. Общее описание

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

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

Таблица 5

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

1.3.2. Соглашения об именовании параметров

В качестве типов для параметров-итераторов 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)). Если сложность алгоритма является постоянной, т. е. не зависит от размера обрабатываемой последовательности, то она не указывается.

1.3.3. Алгоритмы общего назначения

Алгоритмы, описываемые в данном пункте, определены в заголовочном файле <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 присваиваний).