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

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

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

template<class RandomAccessIterator>

void sort(

RandomAccessIterator _First,

RandomAccessIterator _Last

);

template<class RandomAccessIterator, class Predicate>

void sort(

RandomAccessIterator _First,

RandomAccessIterator _Last,

Predicate _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 )

}

Сортировка массива объектов пользовательского класса

// AlgTest.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include "AlgTest.h"

#include <Conio.h>

#include <algorithm> // for_each, find, find_if

#include <vector>

#include <functional> // unary_function

#include <time.h>

/////////////////////////////////////////////////////////////////////

// Сортировка массива объектов пользовательского класса

/////////////////////////////////////////////////////////////////////

/* В классе, имеющем в качестве член-данных указатели,

надо обязательно выполнить перегрузку операции присвоить

и корректно реализовать собственный конструктор копирования.

 */

Struct CMycls // пользовательский класс

{

int *p;

CString Name1;

char * Name2;

float Price;

CMycls()

{

       p=new int [1024];

       TRACE("CMycls()\n");

}

~CMycls()

{

       delete []p;

       TRACE("~CMycls()\n");

}

CMycls(const CMycls & orig)

{

       this->Name1=orig.Name1;

       this->Name2=orig.Name2;

       this->Price=orig.Price;

       this->p=new int [1024];

}

CMycls & operator=(const CMycls & orig)

{

       this->Name1=orig.Name1;

       this->Name2=orig.Name2;

       this->Price=orig.Price;

       if(p) delete []this->p;

       this->p=new int [1024];

       return *this;

}    

};

// PrintArr - печать элементов вектора

void PrintArr(vector <CMycls> & Arr)

{

for(int i=0;i<Arr.size();i++)

{

       wcout<<Arr[i].Name1.GetBuffer();

cout<<' '<<Arr[i].Name2<<' '<<Arr[i].Price<<endl;

}

cout<<endl;

}

// MyCmp - функция предикат, выполняющая сравнение только по одному

// член-данному класса. Если для класса CMycls перегрузить операцию сравнения,

// то можно обойтись без функции MyCmp

bool MyCmp(CMycls& e1,CMycls& e2)

{ // по убыванию (я..а)

return strcmp(e1.Name2,e2.Name2)==1;

}

// BestCmp - функциональный объект, выполняющий сравнение по двум

// член-данным класса в зависимости от значения статического член-данного FNum

Class BestCmp

{

public:

static int FNum;

bool operator ()(const CMycls & e1,const CMycls & e2)

{

       switch(FNum)

       {

       case 2: return strcmp(e1.Name2,e2.Name2)==1;

       case 3: return e1.Price<e2.Price;

       default: return false;

       }

}

};

int BestCmp::FNum;

Void DemoOwnClass()

{

vector <CMycls> Arr;

for(int i=0;i<3; i++)

{

       CMycls * temp=new CMycls;

       Arr.push_back(*temp);

       delete temp;

//     Arr.push_back(*(new CMycls));     

}

Arr[0].Name1="aName1";

Arr[0].Name2="aName2";

Arr[0].Price=123.4;

Arr[1].Name1="bName1";

Arr[1].Name2="bName2";

Arr[1].Price=323.4;

Arr[2].Name1="cName1";

Arr[2].Name2="cName2";

Arr[2].Price=223.4;

//Arr[2]=temp;

cout<<"Arr.size()="<<Arr.size()<<' '<<"Arr.capacity()="<<Arr.capacity()<<endl;

//Arr.size()=3 Arr.capacity()=3

PrintArr(Arr);

//aName1 aName2 123.4

//bName1 bName2 323.4

//cName1 cName2 223.4

swap(Arr[0],Arr[1]);

CMycls swap;

swap=Arr[0];

Arr[0]=Arr[1];

Arr[1]=swap;

PrintArr(Arr);

//bName1 bName2 323.4

//aName1 aName2 123.4

//cName1 cName2 223.4

// сортировка по член-данному Name2

sort(Arr.begin(),Arr.end(),MyCmp);

PrintArr(Arr);

//cName1 cName2 223.4

//bName1 bName2 323.4

//aName1 aName2 123.4

// использование функционального объекта для сортировки по член-данному Price

BestCmp FObj;

BestCmp::FNum=3;

sort(Arr.begin(),Arr.end(),FObj);

PrintArr(Arr);

//aName1 aName2 123.4

//cName1 cName2 223.4

//bName1 bName2 323.4

// Arr.erase(Arr.begin(),Arr.end()); - необязательно

}

Еще одна иллюстрация некоторых алгоритмов на примере обработки числового массива

// AlgTest.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include "AlgTest.h"

#include <Conio.h>

#include <algorithm> // for_each, find, find_if

#include <vector>

#include <functional> // unary_function

#include <time.h>

const int VectorSize =5;

// GreaterThanTwo – (шаблон) объект-функция (предикат), которая возвращает

// значение true, если аргумент превышает значение 2

template <class T>

class GreaterThanTwo : public unary_function<T, bool>

{

public:

bool operator()(T& arg1)

{ return arg1>2; }

};

// ShowElement – шаблонная функция, печатающая значение итератора itor,

// указывающего на элемент последовательности Container. Если значение

// итератора "законечное", то функция выводит строку "Last element!"

template <class Container, class Iterator>

void ShowElement(Container & c, Iterator & itor)

{

if(itor!= c.end()) cout<<*itor; else cout<<"Last element!";

}

/////////////////////////////////////////////////////////////////

Void DemoIntVec()

{

// ExitThread(0);

TCHAR szCurDir[MAX_PATH];

DWORD cchLength = GetFullPathName(TEXT("C:"), MAX_PATH, szCurDir, NULL);

wcout<<szCurDir;

/////////////////////////////////////

vector <int> vInt(VectorSize);

typedef vector <int>::iterator Itor;

for(int i=0; i<VectorSize; i++)vInt[i]=i;

Itor first = vInt.begin();

Itor last = vInt.end();

// вывести все элементы последовательности с помощью for_each

// и объекта-функции DoPrint

cout<<"Test method for_each()\n";

for_each(first,last,DoPrint); // 0 1 2 3 4

cout<<endl;

// найти первый элемент вектора, значение которого равно 2

Itor retItor=find(first,last,2);

cout<<"find(first,last,2)=";

ShowElement(vInt,retItor); //find(first,last,2)=2

cout<<endl;

// найти первый элемент вектора, значение которого равно 10

retItor=find(first,last,10);

cout<<"find(first,last,10)=";

ShowElement(vInt,retItor); //find(first,last,10)=Last element!

cout<<endl;

// найти первый элемент вектора, значение которого больше 2

GreaterThanTwo <int> isGreaterThanTwo;

retItor=find_if(first,last,isGreaterThanTwo);

cout<<"find_if(first,last,isGreaterThanTwo)=";

ShowElement(vInt,retItor);//find_if(first,last,isGreaterThanTwo)=3

cout<<endl;

// подсчитать число элементов вектора, значение которых равно 3

int retSize=count(first,last,3);

cout<<"count(first,last,3)="<<retSize<<endl; //count(first,last,3)=1

// подсчитать число элементов вектора, значение которых больше 2

retSize=count_if(first,last,isGreaterThanTwo);

cout<<"count_if(first,last,isGreaterThanTwo)="<<retSize<<endl;

//count_if(first,last,isGreaterThanTwo)=2

}