10.2.1. Алгоритмы только для чтения

Много алгоритмов только читают значения элементов в исходном диапазоне, но никогда не записывают их. Функция find() и функция count(), использованная в упражнениях раздела 10.1, являются примерами таких алгоритмов.

Другим предназначенным только для чтения алгоритмом является accumulate(), который определен в заголовке numeric. Функция accumulate() получает три аргумента. Первые два определяют диапазон суммируемых элементов, а третий — исходное значение для суммы. Предположим, что vec — это последовательность целых чисел.

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

int sum = accumulate(vec.cbegin(), vec.cend(), 0);

Приведенный выше код суммирует значения элементов вектора vec, используя 0 как начальное значение суммы.

Алгоритмы и типы элементов

У того факта, что функция accumulate() использует свой третий аргумент как отправную точку для суммирования, есть важное последствие: он позволяет добавить тип элемента к типу суммы. Таким образом, тип элементов последовательности должен соответствовать или быть приводим к типу третьего аргумента. В этом примере элементами вектора vec могли бы быть целые числа, или числа типа double, или long long, или любого другого типа, который может быть добавлен к значению типа int.

Например, поскольку тип string имеет оператор +, функцию accumulate() можно использовать для конкатенации элементов вектора строк:

string sum = accumulate(v.cbegin(), v.cend(), string(""));

Этот вызов добавляет каждый элемент вектора v к первоначально пустой строке sum. Обратите внимание: третий параметр здесь явно указан как объект класса string. Передача строки как символьного литерала привела бы к ошибке при компиляции.

// ошибка: no + on const char*

string sum = accumulate(v.cbegin(), v.cend(), "");

Если бы был передан строковый литерал, типом суммируемых значений оказался бы const char*. Этот тип и определяет используемый оператор +. Поскольку тип const char* не имеет оператора +, этот вызов не будет компилироваться.

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

// 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() попытается обратиться к элементам после конца второй последовательности.