Алгоритм partial_sum()

template < class InputIterator, class OutputIterator >

OutputIterator

partial_sum(

InputIterator first, InputIterator last,

OutputIterator result );

template < class InputIterator, class OutputIterator,

class BinaryOperation >

OutputIterator

partial_sum(

InputIterator first, InputIterator last,

OutputIterator result, BinaryOperation op );

Первый вариант partial_sum() создает из последовательности, ограниченной диапазоном [first,last), новую последовательность, в которой значение каждого элемента равно сумме всех предыдущих, включая и данный. Так, из последовательности {0,1,1,2,3,5,8} будет создана {0,1,2,4,7,12,20}, где, например, четвертый элемент равен сумме трех предыдущих (0,1,1) и его самого (2), что дает значение 4.

Во втором варианте вместо оператора сложения используется бинарная операция, заданная программистом. Предположим, мы задали последовательность {1,2,3,4} и объект-функцию times<int>. Результатом будет {1,2,6,24}. В обоих случаях итератор записи OutputIterator указывает на элемент за последним элементом новой последовательности.

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

#include <numeric>

#include <vector>

#include <iostream.h>

/*

* печатается:

элементы: 1 3 4 5 7 8 9

частичная сумма элементов:

1 4 8 13 20 28 37

частичная сумма элементов с использованием times<int>():

1 3 12 60 420 3360 30240

*/

int main()

{

const int ia_size = 7;

int ia[ ia_size ] = { 1, 3, 4, 5, 7, 8, 9 };

int ia_res[ ia_size ];

ostream_iterator< int > outfile( cout, " " );

vector< int, allocator > vec( ia, ia+ia_size );

vector< int, allocator > vec_res( vec.size() );

cout << "элементы: ";

copy( ia, ia+ia_size, outfile ); cout << endl;

cout << "частичная сумма элементов:\n";

partial_sum( ia, ia+ia_size, ia_res );

copy( ia_res, ia_res+ia_size, outfile ); cout << endl;

cout << "частичная сумма элементов с использованием times<int>():\n";

partial_sum( vec.begin(), vec.end(), vec_res.begin(),

times<int>() );

copy( vec_res.begin(), vec_res.end(), outfile );

cout << endl;

}

Алгоритм partition()

template < class BidirectionalIterator, class UnaryPredicate >

BidirectionalIterator

partition(

BidirectionalIterator first,

BidirectionalIterator last, UnaryPredicate pred );

partition() переупорядочивает элементы в диапазоне [first,last). Все элементы, для которых предикат pred равен true, помещаются перед элементами, для которых он равен false. Например, если дана последовательность {0,1,2,3,4,5,6} и предикат, проверяющий целое число на четность, то мы получим две последовательности – {0,2,4,6} и {1,3,5}. Хотя гарантируется, что четные элементы будут помещены перед нечетными, их первоначальное взаимное расположение может и не сохраниться, т.е. 4 может оказаться перед 2, а 5 перед 1. Сохранение относительного порядка обеспечивает алгоритм stable_partition(), рассматриваемый ниже.

#include <algorithm>

#include <vector>

#include <iostream.h>

class even_elem {

public:

bool operator()( int elem )

{ return elem%2 ? false : true; }

};

/*

* печатается:

исходная последовательность:

29 23 20 22 17 15 26 51 19 12 35 40

разбиение, основанное на четности элементов:

40 12 20 22 26 15 17 51 19 23 35 29

разбиение, основанное на сравнении с 25:

12 23 20 22 17 15 19 51 26 29 35 40

*/

int main()

{

const int ia_size = 12;

int ia[ia_size] = { 29,23,20,22,17,15,26,51,19,12,35,40 };

vector< int, allocator > vec( ia, ia+ia_size );

ostream_iterator< int > outfile( cout, " " );

cout << "исходная последовательность: \n";

copy( vec.begin(), vec.end(), outfile ); cout << endl;

cout << "разбиение, основанное на четности элементов:\n";

partition( &ia[0], &ia[ia_size], even_elem() );

copy( ia, ia+ia_size, outfile ); cout << endl;

cout << "разбиение, основанное на сравнении с 25:\n";

partition( vec.begin(), vec.end(), bind2nd(less<int>(),25) );

copy( vec.begin(), vec.end(), outfile ); cout << endl;

}