На этом шаге мы рассмотрим алгоритмы, обратные рассмотренным на предыдущем шаге.

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

  OutputIterator
  adjacent_difference (InputIterator sourceBeg, InputIterator sourceEnd, 
                       OutputIterator destBeg)

  OutputIterator
  adjacent_difference (InputIterator sourceBeg, InputIterator sourceEnd, 
                       OutputIterator destBeg, BinaryFunc op)

Первая форма вычисляет разность между каждым элементом в интервале [sourceBeg,sourceEnd) и его предшественником и записывает результат в приемный интервал [destBeg,...).

Вторая форма вызывает ор для каждого элемента в интервале [sourceBeg, sourceEnd) и его предшественника и записывает результат в приемный интервал [destBeg,...).

Первый элемент просто копируется.

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

  a1 a2 a3 ...

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

  a1, a2 - a1, a3 - а2, ... 
  a1, a2 op а1, a3 op a2, ...

Обе формы возвращают позицию за последним записанным элементом в приемном интервале (то есть позицию первого элемента, который не был заменен).

Первая форма эквивалентна преобразованию серии абсолютных значений в серию относительных значений. В этом отношении алгоритм adjacent_difference() является логическим дополнением алгоритма partial_sum().

Исходный и приемный интервалы могут быть идентичными.

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

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

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

Пример использования алгоритма adjacent_difference():

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

#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()
{
  deque<int> coll;

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

  // Вывод разностей между элементами
  cout << ToRus("Вывод разностей между элементами:\n");
  adjacent_difference (coll.begin(), coll.end(),         // Источник
                       ostream_iterator<int>(cout," ")); // Приемник
  cout << endl;

  // Вывод сумм элементов с их предшественниками
  cout << ToRus("Вывод сумм элементов с их предшественниками:\n");
  adjacent_difference (coll.begin(), coll.end(),         // Источник
                       ostream_iterator<int>(cout," "),  // Приемник
                       plus<int>());                     // Операция
  cout << endl;

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


  getch();
  return 0;
}

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

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

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

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

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

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