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

#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 ele() ); 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;

template < class BidirectionalIterator >

bool

prev permutation( BidirectionalIterator first, BidirectionalIterator last );

template < class BidirectionalIterator, class Compare >

bool

prev permutation( BidirectionalIterator first,

Алгоритм prev permutation()

BidirectionalIterator last, class Compare );

prev permutation() берет последовательность, ограниченную диапазоном [first,last) , и, рассматривая ее как перестановку, возвращает предшествующую ей

#include <algorithm> #include <vector>

#include <iostream.h>

печатается: n d a n a d d n a d a n a n d a d n int main()

vector< char, allocator > vec( 3 ); ostream iterator< char > out stream( cout, );

vec[0] = n; vec[1] = d; vec[2] = a; copy( vec.begin(), vec.end(), out stream ); cout << \t ;

сгенерировать все перестановки dan ile( prev permutation( vec.begin(), vec.end() )) { copy( vec.begin(), vec.end(), out stream );

cout << \t ;

cout << \n\n ; заданная программистом.

template < class RandomAccessIterator > void

random shuffle( RandomAccessIterator first, RandomAccessIterator last );

template < class RandomAccessIterator, class RandomNumberGenerator >

void

random shuffle( RandomAccessIterator first, RandomAccessIterator last,

Алгоритм random shuffle()

RandomNumberGenerator rand);

random shuffle() переставляет элементы из диапазона [first,last) в случайном порядке. Во втором варианте можно передать объект-функцию или указатель на функцию, генерирующую случайные числа. Ожидается, что генератор rand возвращает ; типа double в интервале [0,1].

значение

(о том, как упорядочиваются перестановки, говорилось в разделе 12.5). Если предыдущей перестановки не существует, алгоритм возвращает false, иначе true. В первом варианте для определения предыдущей перестановки используется оператор меньше для типа элементов контейнера, а во втором - бинарная операция сравнения,