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