Язык программирования C++. Пятое издание - Стенли Липпман

// roster2 должен иметь по крайней мере столько же элементов,

// сколько и roster1

equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

Поскольку функция equal() работает с итераторами, ее можно вызвать для сравнения элементов контейнеров разных типов. Кроме того, типы элементов также не обязаны совпадать, пока можно использовать оператор == для их сравнения. Например, контейнер roster1 мог быть вектором vector<string>, а контейнер roster2 — списком list<const char*>.

Однако алгоритм equal() делает критически важное предположение: подразумевает, что вторая последовательность по крайней мере не меньше первой. Этот алгоритм просматривает каждый элемент первой последовательности и подразумевает, что для него есть соответствующий элемент во второй последовательности.

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

Упражнения раздела 10.2.1

Упражнение 10.3. Примените функцию accumulate() для суммирования элементов вектора vector<int>.

Упражнение 10.4. Если вектор v имеет тип vector<double>, в чем состоит ошибка вызова accumulate(v.cbegin(), v.cend(), 0) (если она есть)?

Упражнение 10.5. Что произойдет, если в вызове функции equal() для списков оба из них будут содержать строки в стиле С, а не библиотечные строки?

Ключевая концепция. Итераторы, передаваемые в качестве аргументов

Некоторые алгоритмы читают элементы из двух последовательностей. Составляющие эти последовательности элементы могут храниться в контейнерах различных видов. Например, первая последовательность могла бы быть вектором (vector), а вторая списком (list), двухсторонней очередью (deque), встроенным массивом или другой последовательностью. Кроме того, типы элементов этих последовательностей не обязаны совпадать точно. Обязательно необходима возможность сравнивать элементы этих двух последовательностей. Например, в алгоритме equal() типы элемента не обязаны быть идентичными, на самом деле нужна возможность использовать оператор == для сравнения элементов этих двух последовательностей.

Алгоритмы, работающие с двумя последовательностями, отличаются способом передачи второй последовательности. Некоторые алгоритмы, такие как equal(), получают три итератора: первые два обозначают диапазон первой последовательности, а третий — обозначает первый элемент во второй последовательности. Другие получают четыре итератора: первые два обозначают диапазон элементов в первой последовательности, а вторые два — диапазон второй последовательности.

Алгоритмы, использующие для обозначения второй последовательности один итератор, подразумевают, что вторая последовательность по крайней мере не меньше первой. Разработчик должен сам позаботиться о том, чтобы алгоритм не пытался обратиться к несуществующим элементам во второй последовательности. Например, алгоритм equal() сравнивает каждый элемент первой последовательности с соответствующим элементом второй. Если вторая последовательность является подмножеством первой, то возникает серьезная ошибка — функция equal() попытается обратиться к элементам после конца второй последовательности.

10.2.2. Алгоритмы, записывающие элементы контейнера

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

Некоторые алгоритмы осуществляют запись непосредственно в исходную последовательность. Эти алгоритмы в принципе безопасны: они способны переписать лишь столько элементов, сколько находится в указанном исходном диапазоне.

В качестве примера рассмотрим алгоритм fill(), получающий два итератора, обозначающих диапазон, и третий аргумент, являющийся значением. Функция fill() присваивает данное значение каждому элементу исходной последовательности:

fill(vec.begin(), vec.end(), 0); // обнулить каждый элемент

// присвоить половине последовательности значение 10

fill(vec.begin(), vec.begin() + vec.size()/2, 10);

Поскольку функция fill() пишет в переданную ей исходную последовательность до тех пор, пока она не закончится, запись вполне безопасна.

Алгоритмы не проверяют операции записи

Некоторые алгоритмы получают итератор, обозначающий конкретное назначение. Эти алгоритмы присваивают новые значения элементам последовательности, начиная с элемента, обозначенного итератором назначения. Например, функция fill_n() получает один итератор, количество и значение. Она присваивает предоставленное значение заданному количеству элементов, начиная с элемента, обозначенного итератором. Функцию fill_n() можно использовать для присвоения нового значения элементам вектора:

vector<int> vec; // пустой вектор

// используя вектор vec, предоставить ему разные значения

fill_n(vec.begin(), vec.size(), 0); // обнулить каждый элемент vec

Функция fill_n() подразумевала, что безопасно запишет указанное количество элементов. Таким образом, следующий вызов функции fill_n() подразумевает, что dest указывает на существующий элемент и что в последовательности есть по крайней мере n элементов, начиная с элемента dest.

fill_n(dest, n, val)

Это вполне обычная ошибка для новичка: вызов функции fill_n() (или подобного алгоритма записи элементов) для контейнера без элементов:

vector<int> vec; // пустой вектор

// катастрофа: попытка записи в 10 несуществующих элементов

// вектора vec

fill_n(vec.begin(), 10, 0);

Этот вызов функции fill_n() ведет к катастрофе. Должно быть записано десять элементов, но вектор vec пуст, и никаких элементов в нем нет. Результат непредсказуем, но, вероятнее всего, произойдет серьезный отказ во время выполнения.

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

Функция back_inserter()

Один из способов проверки, имеет ли контейнер достаточно элементов для записи, подразумевает использование итератора вставки (insert iterator), который позволяет добавлять элементы в базовый контейнер. Как правило, при присвоении значения элементу контейнера при помощи итератора осуществляется присвоение тому элементу, на который указывает итератор. При присвоении с использованием итератора вставки в контейнер добавляется новый элемент, равный правому значению.

Более подробная информация об итераторе вставки приведена в разделе 10.4.1. Однако для иллюстрации безопасного применения алгоритмов, записывающих данные в контейнер, используем функцию back_inserter(), определенную в заголовке iterator.

Функция back_inserter() получает ссылку на контейнер и возвращает итератор вставки, связанный с данным контейнером. Попытка присвоения значения элементу при помощи этого итератора приводит к вызову функции push_back(), добавляющей элемент с данным значением в контейнер.

vector<int> vec; // пустой вектор

auto it = back_inserter(vec); // присвоение при помощи it добавляет

                              // элементы в vec

*it = 42; // теперь vec содержит один элемент со значением 42

Функцию back_inserter() зачастую применяют для создания итератора, используемого в качестве итератора назначения алгоритмов. Рассмотрим пример:

vector<int> vec; // пустой вектор

// ok: функция back_inserter() создает итератор вставки,

// который добавляет элементы в вектор vec

fill_n(back_inserter(vec), 10, 0); // добавляет 10 элементов в vec

На каждой итерации функция fill_n() присваивает элемент заданной последовательности. Поскольку ей передается итератор, возвращенный функцией back_inserter(), каждое присвоение вызовет функцию push_back() вектора vec. В результате этот вызов функции fill_n() добавит в конец вектора vec десять элементов, каждый со значением 0.