template < class BidirectionalIterator > bool

next_permutation( BidirectionalIterator first, BidirectionalIterator last );

template < class BidirectionalIterator, class Compare > bool

next_permutation( BidirectionalIterator first,

Алгоритм next_permutation()

BidirectionalIterator last, class Compare );

next_permutation() берет последовательность, ограниченную диапазоном [first,last), и, считая ее перестановкой, возвращает следующую за ней (о том, как упорядочиваются перестановки, говорилось в разделе 12.5). Если следующей перестановки не существует, алгоритм возвращает false, иначе – true. В первом варианте для определения следующей перестановки используется оператор “меньше” в классе элементов контейнера, а во втором – операция сравнения comp.

Последовательные обращения к next_permutation() генерируют все возможные перестановки только в том случае, когда исходная последовательность отсортирована.

Если бы в показанной ниже программе мы предварительно не отсортировали строку musil, получив ilmsu, то не удалось бы сгенерировать все перестановки.

template < class RandomAccessIterator > void

nth_element( RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last );

template < class RandomAccessIterator, class Compare > void

nth_element( RandomAccessIterator first, RandomAccessIterator nth,

Алгоритм nth_element()

RandomAccessIterator last, Compare comp );

nth_element() переупорядочивает последовательность, ограниченную диапазоном [first,last), так что все элементы, меньшие чем тот, на который указывает итератор nth, оказываются перед ним, а все большие элементы – после. Например, если есть

массив

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

то вызов nth_element(), в котором nth указывает на седьмой элемент (его значение равно 26):

nth_element( &ia[0], &ia[6], &ia[2] );

генерирует последовательность, в которой семь элементов, меньших 26, оказываются слева от 26, а четыре элемента, больших 26, справа:

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

При этом не гарантируется, что элементы, расположенные по обе стороны от nth, упорядочены. В первом варианте для сравнения используется оператор “меньше”, определенный для типа элементов контейнера, во втором – бинарная операция сравнения, заданная программистом.

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

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

исходный вектор: 29 23 20 22 17 15 26 51 19 12 35 40

вектор, отсортированный относительно элемента 26 12 15 17 19 20 22 23 26 51 29 35 40

вектор, отсортированный по убыванию относительно элемента 23 40 35 29 51 26 23 22 20 19 17 15 12 */

int main()

{

int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40}; vector< int,allocator > vec( ia, ia+12 ); ostream_iterator<int> out( cout," " );

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

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

cout << "вектор, отсортированный относительно элемента " << *( vec.begin()+6 ) << endl;

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

cout << " вектор, отсортированный по убыванию " << "относительно элемента "

<< *( vec.begin()+6 ) << endl; nth_element( vec.begin(), vec.begin()+6,

vec.end(), greater<int>() );

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

}

template < class RandomAccessIterator > void

partial_sort( RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last );

template < class RandomAccessIterator, class Compare > void

partial_sort( RandomAccessIterator first, RandomAccessIterator middle,

Алгоритм partial_sort()

RandomAccessIterator last, Compare comp );

partial_sort() сортирует часть последовательности, укладывающуюся в диапазон

[first,middle). Элементы в диапазоне [middle,last) остаются неотсортированными. Например, если дан массив

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