то вызов partial_sort(),где middle указывает на шестой элемент:

partial_sort( &ia[0], &ia[5], &ia[12] );

генерирует последовательность, в которой наименьшие пять (т.е. middle-first) элементов отсортированы:

{12,15,17,19,20,29,23,22,26,51,35,40}.

Элементы от middle до last-1 не расположены в каком-то определенном порядке, хотя значения каждого из них лежат вне отсортированной последовательности. В первом варианте для сравнения используется оператор “меньше”, определенный для типа элементов контейнера, а во втором – операция сравнения comp.

template < class InputIterator, class RandomAccessIterator > RandomAccessIterator

partial_sort_copy( InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last );

template < class InputIterator, class RandomAccessIterator, class Compare >

RandomAccessIterator

partial_sort_copy( InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last,

Алгоритм partial_sort_copy()

Compare comp );

partial_sort_copy() ведет себя так же, как partial_sort(), только частично упорядоченная последовательность копируется в контейнер, ограниченный диапазоном [result_first,result_last] (если мы задаем отдельный контейнер для копирования результата, то в нем оказывается упорядоченная последовательность). Например, даны

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

два массива: int ia2[5];

Тогда обращение к partial_sort_copy(), где в качестве middle указан восьмой

partial_sort_copy( &ia[0], &ia[7], &ia[12],

элемент:

&ia2[0], &ia2[5] );

заполняет массив ia2 пятью отсортированными элементами: {12,15,17,19,20}.

#include <algorithm> #include <vector> #include <iostream.h>

/*

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

исходный вектор: 69 23 80 42 17 15 26 51 19 12 35 8

результат применения partial_sort() к вектору: семь элементов

8 12 15 17 19 23 26 80 69 51 42 35

результат применения partial_sort_copy() к первым семи элементам вектора в порядке убывания

26 23 19 17 15 12 8

*/

int main()

{

int ia[] = { 69,23,80,42,17,15,26,51,19,12,35,8 }; vector< int,allocator > vec( ia, ia+12 ); ostream_iterator<int> out( cout," " );

cout << "исходный вектор: ";

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

cout << "результат применения partial_sort() к вектору: " << "семь элементов \n";

partial_sort( vec.begin(), vec.begin()+7, vec.end() ); copy( vec.begin(), vec.end(), out ); cout << endl;

vector< int, allocator > res(7);

cout << " результат применения partial_sort_copy() к первым семи

\n\t"

<< "элементам вектора в порядке убывания \n";

partial_sort_copy( vec.begin(), vec.begin()+7, res.begin(), res.end(), greater<int>() );

copy( res.begin(), res.end(), out ); cout << endl;

Оставшиеся два элемента отсортированы не будут.

}

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,

Алгоритм partial_sum()

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() – это один из численных алгоритмов. Для его использования

#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;

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

}

template < class BidirectionalIterator, class UnaryPredicate > BidirectionalIterator

partition(

BidirectionalIterator first,

Алгоритм partition()

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(), рассматриваемый ниже.