C++ для начинающих

next_permutation( BidirectionalIterator first,

BidirectionalIterator last, class Compare );

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

#include algorithm

#include vector

#include iostream.h

void print_char( char elem ) { cout elem ; }

void (*ppc)( char ) = print_char;

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

ilmsu ilmus ilsmu ilsum ilums ilusm imlsu imlus

imslu imsul imuls imusl islmu islum ismlu ismul

isulm isuml iulms iulsm iumls iumsl iuslm iusml

limsu limus lismu lisum liums liusm lmisu lmius

lmsiu lmsui lmuis lmusi lsimu lsium lsmiu lsmui

lsuim lsumi luims luism lumis lumsi lusim lusmi

milsu milus mislu misul miuls miusl mlisu mlius

mlsiu mlsui mluis mlusi msilu msiul msliu mslui

msuil msuli muils muisl mulis mulsi musil musli

silmu silum simlu simul siulm siuml slimu slium

slmiu slmui sluim slumi smilu smiul smliu smlui

smuil smuli suilm suiml sulim sulmi sumil sumli

uilms uilsm uimls uimsl uislm uisml ulims ulism

ulmis ulmsi ulsim ulsmi umils umisl umlis umlsi

umsil umsli usilm usiml uslim uslmi usmil usmli

*/

int main()

{

vectorchar,allocator vec(5);

// последовательность символов: musil

vec[0] = 'm'; vec[1] = 'u'; vec[2] = 's';

vec[3] = 'i'; vec[4] = 'l';

int cnt = 2;

sort( vec.begin(), vec.end() );

for_each( vec.begin(), vec.end(), ppc ); cout "\t";

// генерируются все перестановки строки "musil"

while( next_permutation( vec.begin(), vec.end()))

{

for_each( vec.begin(), vec.end(), ppc );

cout "\t";

if ( ! ( cnt++ % 8 )) {

cout "\n";

cnt = 1;

}

}

cout "\n\n";

return 0;

}

Алгоритм nth_element()

template class RandomAccessIterator

void

nth_element( RandomAccessIterator first,

RandomAccessIterator nth,

RandomAccessIterator last );

template class RandomAccessIterator, class Compare

void

nth_element( RandomAccessIterator first,

RandomAccessIterator nth,

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_iteratorint 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(), greaterint() );

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

}

Алгоритм partial_sort()

template class RandomAccessIterator