Алгоритм partition()

Алгоритм 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 };

vectorint, allocator vec( ia, ia+ia_size );

ostream_iterator int outfile( cout, " " );

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

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

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

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

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

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

partition( vec.begin(), vec.end(), bind2nd(lessint(),25) );

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

}