Алгоритм sort()

template< class RandomAccessIterator >

void

sort( RandomAccessIterator first,

RandomAccessIterator last );

template< class RandomAccessIterator, class Compare >

void

sort( RandomAccessIterator first,

RandomAccessIterator last, Compare comp );

sort() переупорядочивает элементы в диапазоне [first,last) по возрастанию, используя оператор “меньше”, определенный для типа элементов контейнера. Во втором варианте порядок устанавливается операцией сравнения comp. (Для сохранения относительного порядка равных элементов пользуйтесь алгоритмом stable_sort().) Мы не приводим пример, специально иллюстрирующий применение алгоритма sort(), поскольку его можно найти во многих других программах, в частности в binary_search(), equal_range() и inplace_merge().

Алгоритм stable_partition()

template< class BidirectionalIterator, class Predicate >

BidirectionalIterator

stable_partition( BidirectionalIterator first,

BidirectionalIterator last,

Predicate pred );

stable_partition() ведет себя так же, как partition(), но гарантированно сохраняет относительный порядок элементов контейнера. Вот та же программа, что и для алгоритма partition(), но с использованием stable_partition().

#include <algorithm>

#include <vector>

#include <iostream.h>

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

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

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

устойчивое разбиение по четным элементам:

20 22 26 12 40 29 23 17 15 51 19

устойчивое разбиение по элементам, меньшим 25:

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

*/

class even_elem {

public:

bool operator()( int elem ) {

return elem%2 ? false : true;

}

};

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 > ofile( cout, " " );

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

copy( vec.begin(), vec.end(), ofile ); cout << '\n';

stable_partition( &ia[0], &ia[12], even_elem() );

cout << "устойчивое разбиение по четным элементам:\n";

copy( ia, ia+11, ofile ); cout << '\n';

stable_partition( vec.begin(), vec.end(),

bind2nd(less<int>(),25) );

cout << "устойчивое разбиение по элементам, меньшим 25:\n";

copy( vec.begin(), vec.end(), ofile ); cout << '\n';

}

Алгоритм stable_sort()

template< class RandomAccessIterator >

void

stable_sort( RandomAccessIterator first,

RandomAccessIterator last );

template< class RandomAccessIterator, class Compare >

void

stable_sort( RandomAccessIterator first,

RandomAccessIterator last, Compare comp );

stable_sort() ведет себя так же, как sort(), но гарантированно сохраняет относительный порядок равных элементов контейнера. Второй вариант упорядочивает элементы на основе заданной программистом операции сравнения comp.

#include <algorithm>

#include <vector>

#include <iostream.h>

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

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

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

устойчивая сортировка - по умолчанию в порядке возрастания:

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

устойчивая сортировка: в порядке убывания:

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

*/

int main()

{

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

vector< int, allocator > vec( ia, ia+14 );

ostream_iterator< int > ofile( cout, " " );

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

copy( vec.begin(), vec.end(), ofile ); cout << '\n';

stable_sort( &ia[0], &ia[14] );

cout << "устойчивая сортировка - по умолчанию "

<< "в порядке возрастания:\n";

copy( ia, ia+14, ofile ); cout << '\n';

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

cout << "устойчивая сортировка: в порядке убывания:\n";

copy( vec.begin(), vec.end(), ofile ); cout << '\n';

}