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

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

  #include <numeric>

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

Для выполнения этой операции можно использовать следующие алгоритмы:

  T
  accumulate (InputIterator beg, InputIterator end, 
              T initValue)

  T
  accumulate (InputIterator beg, InputIterator end, 
              T initValue, BinaryFunc op)

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

initValue = initValue + elem

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

  initValue = op(initValue, elem)

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

  a1 a2 a3 a4 ...

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

  initValue + a1 + a2 + аЗ + ... 
  initValue op a1 op a2 op a3 op ...

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

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

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

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

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iterator>
#include "algostuff.hpp"

#include <conio.h> //необходимо для getch()

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
using namespace std;

std::string ToRus(const std::string &in)
{
  char *buff = new char [in.length()+1];
  CharToOem(in.c_str(),buff);
  std::string out(buff);
  delete [] buff;
  return out;
}

int main()
{
  vector<int> coll;

  INSERT_ELEMENTS(coll,1,9);
  PRINT_ELEMENTS(coll,"Исходная коллекция:\n");

  // Вычисление суммы элементов
  cout << ToRus("Сумма элементов: ")
       << accumulate (coll.begin(), coll.end(),    // Интервал
                      0)                           // Начальное значение
       << endl;

  // Вычисление суммы элементов с вычетом 100
  cout << ToRus("Вычисление суммы элементов с вычетом 100: ")
       << accumulate (coll.begin(), coll.end(),    // Интервал
                      -100)                        // Начальное значение
       << endl;

  // Вычисление произведения элементов
  cout << ToRus("Произведение элементов: ")
       << accumulate (coll.begin(), coll.end(),    // Интервал
                      1,                           // Начальное значение
                      multiplies<int>())           // Операция
       << endl;

    // Вычисление произведения элементов (с начальным значением 0)
  cout << ToRus("Произведение элементов\n(с начальным значением 0): ")
       << accumulate (coll.begin(), coll.end(),    // Интервал
                      0,                           // Начальное значение
                      multiplies<int>())           // Операция
       << endl;


  getch();
  return 0;
}

//---------------------------------------------------------------------------

Текст этого примера можно взять здесь.

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

Рис.1. Результат работы приложения

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

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

Предыдущий шаг Содержание Следующий шаг