следует читать: вкчая first и все последующе элементы до last, но не вкчая сам last

границей), как правило, записывается в виде:

[ first, last )

Это означает, что диапазон начинается с first и заканчивается last, однако сам элемент last не включается. Если

first == last то говорят, что диапазон пуст.

К паре итераторов предъявляется такое требование: last должен быть достижим, если начать с first и последовательно применять оператор инкремента. Однако компилятор не может проверить выполнение данного ограничения. Если требование не будет выполнено, поведение программы не определено; обычно это заканчивается ее крахом и дампом памяти.

В объявлении каждого алгоритма подразумевается минимальная поддержка, которую должны обеспечить итераторы (краткое обсуждение пяти категорий итераторов см. в разделе 12.4). Например, алгоритм find(), реализующий однопроходный обход контейнера и выполняющий только чтение, требует итератора чтения InputIterator. Ему также можно передать одно- или двунаправленный итератор или итератор с произвольным доступом. Однако передача итератора записи приведет к ошибке. Не гарантируется, что подобные ошибки (при передаче итератора неподходящей категории) будут обнаружены компилятором, поскольку категории итераторов - это не сами тины, а лишь параметры, которыми конкретизируется шаблон функции.

Некоторые алгоритмы существуют в нескольких вариантах: в одном используется тот или иной встроенный оператор, а в другом - объект-функция или указатель на функцию, реализующие альтернативу этому оператору. Например, алгоритм unie () по умолчанию сравнивает соседние элементы контейнера с помощью оператора

Приложение

21. Обобщенные алгоритмы в алфавитном порядке

В этом Приложении мы рассмотрим все алгоритмы. Mi решили расположить их в алфавитном порядке (за небольшими исключениями), чтобы проще б1ло найти нужный. Каждый алгоритм представлен в следующем виде: сначала описывается прототип функции, затем сам алгоритм, причем особое внимание уделяется интуитивно неочевидн1м особенностям, и, наконец, приводится пример программы, показывающий, как можно данный алгоритм использовать.

Первыми двумя аргументами всех обобщенных алгоритмов (естественно, не без исключений) является пара итераторов, обгчно first и last, обозначающих диапазон элементов внутри контейнера или встроенного массива, над которым работает алгоритм. Этот диапазон (часто называемый интервалом с включенной левой

равенства, определенного в классе, к которому данные элементы принадлежат. Но если в этом классе нет оператора равенства или мы хотим сравнивать элементы иным способом, то можем передать объект-функцию или указатель на функцию, поддерживающую нужную семантику. Есть и такие алгоритмы, которые выполняют похожие действия, но имеют различные имена. Так, имена предикатных версий алгоритмов всегда заканчиваются на if, скажем find if(). Например, есть вариант алгоритма replace(), где используется встроенный оператор равенства, и вариант с именем replace if() , которому передается предикатный объект-функция или указатель на функцию-предикат.

Алгоритмы, модифицирующие контейнер, обычно также существуют в двух вариантах: один осуществляет модификацию по месту, а второй возвращает копию с внесенными изменениями. Так, есть алгоритмы replace() и replace copy (). Однако вариант с копированием (его имя всегда содержит слово copy) имеется не для каждого алгоритма, модифицирующего контейнер. К примеру, для алгоритмов sort() его нет. В таких случаях, если нужно, чтобы алгоритм работал с копией, мы должны создать ее самостоятельно и передать в качестве аргумента.

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

#include <algorithm>

Для употребления любого из четырех численных алгоритмов: adjacent difference(), accumulate(), inner product() и partial sum () -нужно включить также файл

#include <numeric>

Приведенные в этом Приложении примеры программ, в которых используются алгоритмы и различные контейнерные типы, отражают существующую на момент написания книги реализацию. Применение библиотеки ввода/вывода iostream следует соглашениям, установленным до принятия стандарта; скажем, в программу включается заголовочный файл iostream.h, а не iostream. Шаблоны не поддерживают аргументы по умолчанию. Чтобы программа работала на системе, имеющейся у вас, возможно, придется изменить некоторые объявления.

Другое, более подробное, чем в этой книге, описание обобщенных алгоритмов можно найти в работе [MUSSER96], правда, оно несколько отстает от окончательного варианта стандартной библиотеки C++.

Алгоритм accumulate()

template < class InputIterator, class Type > Type accumulate(

InputIterator first, InputIterator last,

Type init );

template < class InputIterator, class Type,

class BinaryOperation > Type accumulate(

InputIterator first, InputIterator last,

Type init, BinaryOperation op );

Первый вариант accumulate() вычисляет сумму значений элементов последовательности из диапазона, ограниченного парой итераторов [first,last) , с начальным значением, которое задано параметром init. Например, если дана последовательность {1,1,2,3,5,8} и начальное значение 0, то результатом работы алгоритма будет 20. Во втором варианте вместо оператора сложения к элементам применяется переданная бинарная операция. Если бы мы передали алгоритму accumulate() объект-функцию times<int> и начальное значение 1, то получили бы результат 240. accumulate() - это один из численных алгоритмов; для его

#include <numeric> #include <list> #include <functional> #include <iostream.h>

* в1ход:

* accumulate()

* работает с последовательностью {1,2,3,4}

* результат для сложея по умолча: 10

* результат для объекта-функц plus<int>: 10

int main()

int ia[] = { 1, 2, 3, 4 };

list<int,allocator> ilist( ia, ia+4 );

int ia result = accumulate(&ia[0], &ia[4], 0); int ilist res = accumulate( ilist.begin(), ilist.end(), 0, plus<int>() );

cout

< accumulate()\n\t

< работает с последовательностью {1,2,3,4}\n\t

< результат для сложения по умолчанию:

< ia result << \n\t

< результат для объекта-функции plus<int>:

< ilist res

< endl;

return 0;

использования в программу необходимо включить заголовочный файл <numeric>.