16.13. Шаблон класса Array

16.13. Шаблон класса Array

В этом разделе мы завершим реализацию шаблона класса Array, введенного в разделе 2.5 (этот шаблон будет распространен на одиночное наследование в разделе 18.3 и на множественное наследование в разделе 18.6). Так выглядит полный заголовочный файл:

#ifndef ARRAY_H

#define ARRAY_H

#include iostream

template class elemType class Array;

template class elemType ostream&

operator( ostream &, Array&elemType& & );

template class elemType

class Array {

public:

explicit Array( int sz = DefaultArraySize )

{ init( 0, sz ); }

Array( const elemType *ar, int sz )

{ init( ar, sz ); }

Array( const Array &iA )

{ init( iA._ia, iA._size ); }

~Array() { delete[] _ia; }

Array & operator=( const Array & );

int size() const { return _size; }

elemType& operator[]( int ix ) const

{ return _ia[ix]; }

ostream &print( ostream& os = cout ) const;

void grow();

void sort( int,int );

int find( elemType );

elemType min();

elemType max();

private:

void init( const elemType*, int );

void swap( int, int );

static const int DefaultArraySize = 12;

int _size;

elemType *_ia;

};

#endif

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

template class elemType

void ArrayelemType::init( const elemType *array, int sz )

{

_size = sz;

_ia = new elemType[ _size ];

for ( int ix = 0; ix _size; ++ix )

if ( ! array )

_ia[ ix ] = 0;

else _ia[ ix ] = array[ ix ];

}

Реализация копирующего оператора присваивания не вызывает затруднений. Как отмечалось в разделе 14.7, в код включена защита от копирования объекта в самого себя:

template class elemType ArrayelemType&

ArrayelemType::operator=( const ArrayelemType&iA )

{

if ( this != &iA ) {

delete[] _ia;

init( iA._ia, iA._size );

}

return *this;

}

Функция-член print() отвечает за вывод объекта того типа, которым конкретизирован шаблон Array. Возможно, реализация несколько сложнее, чем необходимо, зато данные аккуратно размещаются на странице. Если экземпляр конкретизированного класса Array содержит элементы 3, 5, 8, 13 и 21, то выведены они будут так:

(5) 3, 5, 8, 13, 21

Оператор потокового вывода просто вызывает print(). Ниже приведена реализация обеих функций:

template class elemType ostream&

operator( ostream &os, Array&elemType& &ar )

{

return ar.print( os );

}

template class elemType

ostream & Array&elemType&::print( ostream &os ) const

{

const int lineLength = 12;

os "( " _size " ) ";

for ( int ix = 0; ix _size; ++ix )

{

if ( ix % lineLength == 0 && ix )

os " ";

os _ia[ ix ];

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

// а также за последним элементом массива

if ( ix % lineLength != lineLength-1 && ix != _size-1 )

os ", ";

}

os " ";

return os;

}

Вывод значения элемента массива в функции print() осуществляет такая инструкция:

os _ia[ ix ];

Для ее правильной работы должно выполняться требование к типам, которыми конкретизируется шаблон Array: такой тип должен быть встроенным либо иметь собственный оператор вывода. В противном случае любая попытка распечатать содержимое класса Array приведет к ошибке компиляции в том месте, где используется несуществующий оператор.

Функция-член grow() увеличивает размер объекта класса Array. В нашем примере - в полтора раза:

template class elemType

void Array elemType::grow()

{

elemType *oldia = _ia;

int oldSize = _size;

_size = oldSize + oldSize/2 + 1;

_ia = new elemType[_size];

int ix;

for ( ix = 0; ix oldSize; ++ix )

_ia[ix] = oldia[ix];

for ( ; ix _size; ++ix )

_ia[ix] = elemType();

delete[] oldia;

}

Функции-члены find(), min() и max() осуществляют последовательный поиск во внутреннем массиве _ia. Если бы массив был отсортирован, то, конечно, их можно было бы реализовать гораздо эффективнее.

template class elemType

elemType Array elemType ::min( )

{

assert( _ia != 0 );

elemType min_val = _ia[0];

for ( int ix = 1; ix _size; ++ix )

if ( _ia[ix] min_val )

min_val = _ia[ix];

return min_val;

}

template class elemType

elemType Array elemType ::max()

{

assert( _ia != 0 );

elemType max_val = _ia[0];

for ( int ix = 1; ix _size; ++ix )

if ( max_val _ia[ix] )

max_val = _ia[ix];

return max_val;

}

template class elemType

int Array elemType ::find( elemType val )

{

for ( int ix = 0; ix _size; ++ix )

if ( val == _ia[ix] )

return ix;

return -1;

}

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

template class elemType

void Array elemType ::swap( int i, int j )

{

elemType tmp = _ia[i];

_ia[i] = _ia[j];

_ia[j] = tmp;

}

template class elemType

void Array elemType ::sort( int low, int high )

{

if ( low = high ) return;

int lo = low;

int hi = high + 1;

elemType elem = _ia[low];

for ( ;; ) {

while ( _ia[++lo] elem ) ;

while ( _ia[--hi] elem ) ;

if ( lo hi )

swap( lo,hi );

else break;

}

swap( low, hi );

sort( low, hi-1 );

sort( hi+1, high );

}

То, что код реализован, разумеется, не означает, что он работоспособен. try_array() - это шаблон функции, предназначенный для тестирования реализации шаблона Array:

#include "Array.h"

template class elemType

void try_array( Array elemType &iA )

{

cout "try_array: начальные значения массива ";

cout iA endl;

elemType find_val = iA [ iA.size()-1 ];

iA[ iA.size()-1 ] = iA.min();

int mid = iA.size()/2;

iA[0] = iA.max();

iA[mid] = iA[0];

cout "try_array: после присваиваний ";

cout iA endl;

ArrayelemType iA2 = iA;

iA2[mid/2] = iA2[mid];

cout "try_array: почленная инициализация ";

cout iA endl;

iA = iA2;

cout "try_array: после почленного копирования ";

cout iA endl;

iA.grow();

cout "try_array: после вызова grow ";

cout iA endl;

int index = iA.find( find_val );

cout "искомое значение: " find_val;

cout " возвращенный индекс: " index endl;

elemType value = iA[index];

cout "значение элемента с этим индексом: ";

cout value endl;

}

Рассмотрим шаблон функции try_array(). На первом шаге печатается исходный объект Array, что подтверждает успешную конкретизацию оператора вывода шаблона, а заодно дает начальную картину, с которой можно будет сверяться при последующих модификациях. В переменной find_val хранится значение, которое мы впоследствии передадим find(). Если бы try_array() была обычной функцией, роль такого значения сыграла бы константа. Но поскольку никакая константа не может обслужить все типы, которыми допустимо конкретизировать шаблон, то приходится выбирать другой путь. Далее одним элементам Array случайным образом присваиваются значения других элементов, чтобы протестировать min(), max(), size() и, конечно, оператор взятия индекса.

Затем объект iA2 почленно инициализируется объектом iA, что приводит к вызову копирующего конструктора. После этого тестируется оператор взятия индекса с объектом ia2: производится присваивание элементу с индексом mid/2. (Эти две строки представляют интерес в случае, когда iA - производный подтип Array, а оператор взятия индекса объявлен виртуальной функцией. Мы вернемся к этому в главе 18 при обсуждении наследования.) Далее в iA почленно копируется модифицированный объект iA2, что приводит к вызову копирующего оператора присваивания класса Array. Затем проверяются функции-члены grow() и find(). Напомним, что find() возвращает значение -1, если искомый элемент не найден. Попытка выбрать из "массива" Array элемент с индексом -1 приведет к выходу за левую границу. (В главе 18 для перехвата этой ошибки мы построим производный от Array класс, который будет проверять выход за границы массива.)

Убедиться, что наша реализация шаблона работает для различных типов данных, например целых чисел, чисел с плавающей точкой и строк, поможет программа main(), которая вызывает try_array() с каждым из указанных типов:

#include "Array.C"

#include "try_array.C"

#include string

int main()

{

static int ia[] = { 12,7,14,9,128,17,6,3,27,5 };

static double da[] = { 12.3,7.9,14.6,9.8,128.0 };

static string sa[] = {

"Eeyore", "Pooh", "Tigger",

"Piglet", "Owl", "Gopher", "Heffalump"

};

Array int iA( ia, sizeof(ia)/sizeof(int) );

Array double dA( da, sizeof(da)/sizeof(double) );

Array string sA( sa, sizeof(sa)/sizeof(string) );

cout "template Arrayint class " endl;

try_array(iA);

cout "template Arraydouble class " endl;

try_array(dA);

cout "template Arraystring class " endl;

try_array(sA);

return 0;

}

Вот что программа выводит при конкретизации шаблона Array типом double:

try_array: начальные значения массива

( 5 ) 12.3, 7.9, 14.6, 9.8, 128

try_array: после присваиваний

( 5 ) 14.6, 7.9, 14.6, 9.8, 7.9

try_array: почленная инициализация

( 5 ) 14.6, 7.9, 14.6, 9.8, 7.9

try_array: после почленного копирования

( 5 ) 14.6, 14.6, 14.6, 9.8, 7.9

try_array: после вызова grow

( 8 ) 14.6, 14.6, 14.6, 9.8, 7.9, 0, 0, 0

искомое значение: 128 возвращенный индекс: -1

значение элемента с этим индексом: 3.35965e-322

Выход индекса за границу массива приводит к тому, что последнее напечатанное программой значение неверно. Конкретизация шаблона Array типом string заканчивается крахом программы:

template Arraystring class

try_array: начальные значения массива

( 7 ) Eeyore, Pooh, Tigger, Piglet, Owl, Gopher, Heffalump

try_array: после присваиваний

( 7 ) Tigger, Pooh, Tigger, Tigger, Owl, Gopher, Eeyore

try_array: почленная инициализация

( 7 ) Tigger, Pooh, Tigger, Tigger, Owl, Gopher, Eeyore

try_array: после почленного копирования

( 7 ) Tigger, Tigger, Tigger, Tigger, Owl, Gopher, Eeyore

try_array: после вызова grow

( 11 ) Tigger, Tigger, Tigger, Tigger, Owl, Gopher, Eeyore, пусто , пусто , пусто , пусто

искомое значение: Heffalump возвращенный индекс: -1

Memory fault (coredump)

Упражнение 16.11

Измените шаблон класса Array, убрав из него функции-члены sort(), find(), max(), min() и swap(), и модифицируйте шаблон try_array() так, чтобы она вместо них пользовалась обобщенными алгоритмами (см. главу 12).

2011-09-05 16:08:36 Алексей

Спасибо за статью. Было интересно и полезно.