Численные алгоритмы

В этом разделе представлены алгоритмы STL, предназначенные для обработки числовых данных. Впрочем, с их помощью можно обрабатывать и другую информацию. Например, алгоритм accumulate() может применяться для конкатенации строк. Чтобы использовать числовые алгоритмы, в программу необходимо включить заголовочный файл <numeric>:

#includG <nurner1c>

Обработка интервалов

Вычисление результата по одному интервалу

accumulate (Inputlterator beg. Inputlterator end. T initValue)

accumulate (Inputlterator beg. Inputlterator end. T initVdlue. BinaryFunc op)

О Первая форма вычисляет и возвращает сумму initValue и всех элементов в интервале lbeg,end). Для каждого элемента выполняется команда:

initValue = initValue + elem

О Вторая форма вычисляет и возвращает накопленный результат вызова ор для initValue и каждого элемента в интервале [beg,end). Для каждого элемента выполняется команда:

initValue = opdnitValue, elem)

О Таким образом, пусть мы имеем следующие значения:

al а2 аЗ а4,,,

Для этих значений соответственно вычисляются и записываются такие величины:

initValue + al + а2 + аЗ + .,. initValue ор al ор а2 ор вЗ ор ...

О Для пустого интервала (beg end) обе формы возвращают initValue.

О Предикат ор не должен модифицировать передаваемые аргументы.

О Сложность линейная (numberOfElements вызовов оператора + или opQ соответственно).

В исходной версии STL численные алгоритмы определялись в заголовочном файле <aIgo.h>.

В следующем примере алгоритм accumulate() используется для вычисления суммы и произведения всех элементов интервала.

algo/accul.cpp finclude "algostuff.hpp" using namespace std;

int maln() {

vector<int> coll;

INSERTjLEMENTS(col 1.1.9); PRINTJLEMENTSCcoll):

Вычисление суммы элементов cout « "sum; "

« accumulate CcoU.beginO, coll.endC). Интервал

0) Начальное значение

« endl;

Вычисление суммы элементов с вычетом 100 cout « "sum: "

« accumulate CcoU.beginO. coll.endC), Интервал

-100) Начальное значение

« endl;

Вычисление произведения элементов cout « "product: "

« accumulate Ccoll.beginC). coll.endC). Интервал

1. Начальное значение

multiplies<int>C)) Операция

« endl:

Вычисление произведения элементов Сс начальным значением 0) cout « "product: "

« accumulate Ccoll.beginC). coll.endC), Интервал

0. Начальное значение

multiplies<int>C)) Операция

« endl;

Результат выполнения программы выглядит так:

1 2 3 4 5 6 7 8 9 sum: 45 sum: -55 product: 362880 product; О

Последнее произведение равно нулю, поскольку при умножении любого числа на ноль результат равен нулю.

Вычисление скалярного произведения двух интервалов

1nner procluct (Inputlteratorl begl. Inputlteratorl endl. Inputlterator? beg2. T initValue)

inner product (Inputlteratorl begl. Inputlteratorl endl. lnputIterator2 beg2. T initValue. BinaryFunc opl. BinaryFunc op2)

О Первая форма вычисляет и возвращает скалярное произведение initValue и элементов интервалов \beg,end) и [beg2,...). Для каждого элемента выполняется команда:

initValue = initValue + eleml * elem2

О Вторая форма вычисляет и возвращает накопленный результат вызова ор для initValue и элементов интервала [beg,end), объединенных с элементами [beg2,...). Для каждого элемента выполняется команда:

initValue = opl{initValue.op2{eleml .elem2))

О Таким образом, пусть мы имеем следующие значения:

al а2 аЗ а4... Ы Ь2 ЬЗ ...

Для этих значений соответственно вычисляются и записываются такие величины:

imtValue + (al * bl) + (а2 * Ь2) + (аЗ * ЬЗ) + ...

initValue opl (al ор2 bl) opl (a2 op2 b2) opl (аЗ op2 ЬЗ) opl .,.

О Для пустого первого интервала (begl endl) обе формы возвращают initValue.

О Перед вызовом необходимо убедиться в том, что интервал [beg2,...) содержит достаточное количество элементов.

О Предикаты ор1 п ор2 не должны модифицировать передаваемые аргументы.

О Сложность линейная (numberOfElements вызовов операторов + и * или numberOfElements вызовов op1Q и ор2() соответственно).

В следующем примере алгоритм inner product() используется для вычисления суммы произведений и произведения сумм элементов двух интервалов.

algo/innerl.cpp #include "algostuff.hpp" using namespace std:

int mainO

list<int> coll;

INSERT ELEMENTS(coll.l.6):