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

В главе 6 мы видели, что в стандартной библиотеке C++ определен контейнерный тип vector, который ведет себя во многом аналогично типу Array. В главе 12 рассматриваются обобщенные алгоритмы, способные манипулировать контейнерами, описанными в главе 6. Один из таких алгоритмов, sort(), служит для сортировки содержимого вектора. В этом разделе мы определим собственный “обобщенный алгоритм sort()” для манипулирования классом Array, упрощенной версии алгоритма из стандартной библиотеки C++.

Шаблон функции sort() для шаблона класса Array определен следующим образом:

template class elemType

void sort( ArrayelemType array, int low, int high ) {

if ( low high ) {

int lo = low;

int hi = high + 1;

elemType elem = array[lo];

for (;;) {

while ( min( array[++lo], elem ) != elem lo high ) ;

while ( min( array[--hi], elem ) == elem hi low ) ;

if (lo hi)

swap( array, lo, hi );

else break;

}

swap( array, low, hi );

sort( array, low, hi-1 );

sort( array, hi+1, high );

}

}

В sort() используются две вспомогательные функции: min() и swap(). Обе они должны определяться как шаблоны, чтобы иметь возможность обрабатывать любые типы фактических аргументов, с которыми может быть конкретизирован шаблон sort(). min() определена как шаблон функции для поиска минимального из двух значений любого типа:

template class Type

Type min( Type a, Type b ) {

return a b ? a : b;

}

swap() – шаблон функции для перестановки двух элементов массива любого типа:

template class elemType

void swap( ArrayelemType array, int i, int j )

{

elemType tmp = array[ i ];

array[ i ] = array[ j ];

array[ j ] = tmp;

}

Убедиться в том, что функция sort() действительно работает, можно с помощью отображения содержимого массива после сортировки. Поскольку функция display() должна обрабатывать любой массив, конкретизированный из шаблона класса Array, ее тоже следует определить как шаблон:

#include iostream

template class elemType

void display( ArrayelemType array )

{ //формат отображения: 0 1 2 3 4 5

cout " ";

for ( int ix = 0; ix array.size(); ++ix )

cout array[ix] " ";

cout "\n";

}

В этом примере мы пользуемся моделью компиляции с включением и помещаем шаблоны всех функций в заголовочный файл Array.h вслед за объявлением шаблона класса Array.

Следующий шаг – написание функции для тестирования этих шаблонов. В sort() поочередно передаются массивы элементов типа double, типа int и массив строк. Вот текст программы:

#include iostream

#include string

#include "Array.h"

double da[10] = {

26.7, 5.7, 37.7, 1.7, 61.7, 11.7, 59.7,

15.7, 48.7, 19.7 };

int ia[16] = {

503, 87, 512, 61, 908, 170, 897, 275, 653,

426, 154, 509, 612, 677, 765, 703 };

string sa[11] = {

"a", "heavy", "snow", "was", "falling", "when",

"they", "left", "the", "police", "station" };

int main() {

// вызвать конструктор для инициализации arrd

Arraydouble arrd( da, sizeof(da)/sizeof(da[0]) );

// вызвать конструктор для инициализации arri

Arrayint arri( ia, sizeof(ia)/sizeof(ia[0]) );

// вызвать конструктор для инициализации arrs

Arraystring arrs( sa, sizeof(sa)/sizeof(sa[0]) );

cout "sort array of doubles (size == "

arrd.size() ")" endl;

sort(arrd, 0, arrd.size()-1 );

display(arrd);

cout "sort array of ints (size == "

arri.size() ")" endl;

sort(arri, 0, arri.size()-1 );

display(arri);

cout "sort array of strings (size == "