21.7.Пример использования шаблонной функции sort() из библиотеки алгоритмов

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

Объявление функции:

template<class RandomAccessIterator>

void sort(

RandomAccessIterator _First,

RandomAccessIterator _Last

);

template<class RandomAccessIterator, class Predicate>

void sort(

RandomAccessIterator _First,

RandomAccessIterator _Last,

Predicate _Comp

);

Параметры функции

_First	Итератор произвольного доступа, указывающий на позицию первого элемента в сортируемом диапазоне значений контейнера
_Last	Итератор произвольного доступа, указывающий на позицию последнего элемента в сортируемом диапазоне значений контейнера
_Comp	Определенная программистом функция-предикат, которая должна выполнять сравнение в соответствии с требуемым критерием. Эта функция должна иметь два параметра и должна возвращать значение булевского типа в зависимости от результатов сравнения переданных ей значений.

Замечания:

Заданный диапазон сортировки должен быть корректным и последний элемент диапазона должен быть достигаем путем инкрементирования итератора, указывающего на первое значение.

Сортируемые элементы эквивалентны, но не обязательно равны, если ни один не меньше другого. Алгоритм сортировки не является стабильным и, следовательно, не гарантирует того, что относительный порядок эквивалентных элементов будет сохранен. Для сохранения относительного порядка используйте алгоритм stable_sort.

Средняя сложность сортировки O(N log N), где N = _Last – _First.

Пример программы (см. проект AlgTest):

#include <vector>

#include <algorithm>

#include <functional> // Для greater<int>( )

#include <iostream>

using namespace std;

// Определенный программистом предикат

bool UDgreater ( int elem1, int elem2 )

{

return elem1 > elem2;

}

int main( )

{

vector <int> v1;

vector <int>::iterator Iter;

int i;

for ( i = 0 ; i <= 5 ; i++ ) v1.push_back( 2 * i );

for ( i = 0 ; i <= 5 ; i++ ) v1.push_back( 2 * i + 1 );

cout << "Original vector v1 = ( " ;

for ( Iter = v1.begin( ) ; Iter != v1.end( ) ; Iter++ ) cout << *Iter << " ";

cout << ")" << endl;

// Original vector v1 = ( 0 2 4 6 8 10 1 3 5 7 9 11 )

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

cout << "Sorted vector v1 = ( " ;

for ( Iter = v1.begin( ) ; Iter != v1.end( ) ; Iter++ ) cout << *Iter << " ";

cout << ")" << endl;

// Sorted vector v1 = ( 0 1 2 3 4 5 6 7 8 9 10 11 )

// Для сортировки в убывающем порядке надо указать предикат

sort( v1.begin( ), v1.end( ), greater<int>( ) );

cout << "Resorted (greater) vector v1 = ( " ;

for ( Iter = v1.begin( ) ; Iter != v1.end( ) ; Iter++ ) cout << *Iter << " ";

cout << ")" << endl;

// Resorted (greater) vector v1 = ( 11 10 9 8 7 6 5 4 3 2 1 0 )

// Использование определенного программистом предиката

sort( v1.begin( ), v1.end( ), UDgreater );

cout << "Resorted (UDgreater) vector v1 = ( " ;

for ( Iter = v1.begin( ) ; Iter != v1.end( ) ; Iter++ ) cout << *Iter << " ";

cout << ")" << endl;

// Resorted (UDgreater) vector v1 = ( 11 10 9 8 7 6 5 4 3 2 1 0 )

}