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

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

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

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

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

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

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

Тип третьего аргумента функции accumulate()определяет, какой именно оператор суммы будет использован и каков будет тип возвращаемого значения функции accumulate().

У того факта, что функция 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*не имеет оператора +, этот вызов не будет компилироваться.

С алгоритмами, которые читают, но не пишут в элементы, обычно лучше использовать функции cbegin()и cend()(см. раздел 9.2.3). Но если возвращенный алгоритмом итератор планируется использовать для изменения значения элемента, то следует использовать функции begin()и end().

Алгоритмы, работающие с двумя последовательностями

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

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

// сколько и roster1

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

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

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

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

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

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

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

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

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

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