Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ТЕМА КУРСОВОЙ РАБОТЫ

ШАБЛОН ИЕРАРХИЧЕСКОЙ СТРУКТУРЫ ДАННЫХ В ПАМЯТИ



ОГЛАВЛЕНИЕ

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

1. НАЗНАЧЕНИЕ И ОБЛАСТЬ ПРИМЕНЕНИЯ ПРОГРАММНОГО ПРОДУКТА

2. ВЫБОР И ОБОСНОВАНИЕ ВЫБОРА ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ

3. ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ

3.1 Определение шаблона класса

3.2 Определения шаблонов классов Queue и QueueItem

3.3 Аргументы шаблона для параметров-констант

3.4 Конкретизация шаблона класса

3.5 Функции-члены шаблонов классов

3.6 Функции-члены шаблонов Queue и QueueItem

3.7 Объявления друзей в шаблонах классов

3.8 Объявления друзей в шаблонах Queue и QueueItem

3.9 Статические члены шаблонов класса

3.10 Вложенные типы шаблонов классов

3.11 Шаблоны-члены

3.12 Шаблоны классов и модель компиляции A

3.13 Модель компиляции с включением

3.14 Модель компиляции с разделением

3.15 Явные объявления конкретизации

4. СТРУКТУРНОЕ ОПИСАНИЕ РАЗРАБОТКИ

5. ИЕРАРХИЯ КЛАССОВ

6. ОПИСАНИЕ ПРОГРАММЫ

7. ОПИСАНИЕ АЛГОРИТМОВ И МЕТОДОВ РЕШЕНИЯ. ФУНКЦИОНАЛЬНОЕ ОПИСАНИЕ

7.1 Class CyDoublewayList

7.2 Class StartMenu

7.3 Class StringMy

8. ОПИСАНИЕ ПОЛЬЗОВАТЕЛЬСКОГО ИНТЕРФЕЙСА

9. ОПИСАНИЕ РАБОТЫ ПРОГРАММЫ НА КОНТРОЛЬНЫХ ПРИМЕРАХ

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

ТЕКСТЫ ПРОГРАММНЫХ МОДУЛЕЙ (ПРИЛОЖЕНИЕ)



ТЕХНИЧЕСКОЕ ЗАДАНИЕ

Для заданной двухуровневой структуры данных, содержащей указатели на объекты (или сами объекты) - параметры шаблона, разработать полный набор операций (добавление, включение и извлечение по логическому номеру, сортировка, включение с сохранением порядка, загрузка и сохранение строк в бинарном файле, балансировка - выравнивание размерностей структур данных нижнего уровня). Предполагается, что операции сравнения хранимых объектов переопределены стандартным образом (в виде операций <,> и т.д.). Программа должна использовать шаблонный класс с объектами-строками и реализовывать указанные выше действия над текстом любого объема, загружаемого из файла.

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

Вариант 5

Шаблон структуры данных - двусвязный циклический список, каждый элемент которого содержит статический массив указателей на объекты. Последовательность указателей в каждом массиве ограничена NULL. При переполнении текущего массива указателей создается новый элемент списка, в который переписывается половина указателей из текущего.



1. НАЗНАЧЕНИЕ И ОБЛАСТЬ ПРИМЕНЕНИЯ ПРОГРАММНОГО ПРОДУКТА

Данный программный продукт предназначен для обработки строк внесённых в шаблон построенный на базе списка массивов. И в качестве наглядного пособия при изучении механизма шаблонов в языке программирования С++.

программирование пользовательский интерфейс С++



2. ВЫБОР И ОБОСНОВАНИЕ ВЫБОРА ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ

Программа создана с использованием лицензионных инструментальных средств фирмы Microsoft (Рис 1.). Выбор обоснован удобным дебаггером и наличием студенческой лицензии.

Рис.1 Средства, используемые в разработке.



3. ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ

Матерьял представленный в этом разделе даёт представление о шаблонах классов в С++, содержит примеры исходного кода поясняющие важные места.

Шаблон - это предписание для создания класса, в котором один или несколько типов либо значений параметризованы.

Начинающий программист может использовать шаблоны, не понимая механизма, стоящего за их определениями и конкретизациями. Только профессиональные программисты определяют собственные шаблоны классов и пользуются описанными в ниже средствами. Поэтому этот материал следует рассматривать как введение в более сложные аспекты C++.

3.1 Определение шаблона класса

Предположим, что нам нужно определить класс, поддерживающий механизм очереди. Очередь - это структура данных для хранения коллекции объектов; они помещаются в конец очереди, а извлекаются из ее начала. Поведение очереди описывают аббревиатурой FIFO - "первым пришел, первым ушел". (Определенный в стандартной библиотеке C++ тип, реализующий очередь, упоминался в разделе 6.17. В этой главе мы создадим упрощенный тип для знакомства с шаблонами классов.)

Необходимо, чтобы наш класс Queue поддерживал следующие операции:

1. добавить элемент в конец очереди:

void add( item );

2. удалить элемент из начала очереди:



item remove();

3. определить, пуста ли очередь:

bool is_empty();

4. определить, заполнена ли очередь:

bool is_full();

Определение Queue могло бы выглядеть так:

class Queue {

public:

Queue();

~Queue();

Type& remove();

void add( const Type & );

bool is_empty();

bool is_full();

private:

// ...

};

Вопрос в том, какой тип использовать вместо Type? Предположим, что мы решили реализовать класс Queue, заменив Type на int. Тогда Queue может управлять коллекциями объектов типа int. Если бы понадобилось поместить в очередь объект другого типа, то его пришлось бы преобразовать в тип int, если же это невозможно, компилятор выдаст сообщение об ошибке:



Queue qObj;

string str( "vivisection" );

qObj.add( 3.14159 ); // правильно: в очередь помещен объект 3

qObj.add( str );// ошибка: нет преобразования из string в int

Поскольку любой объект в коллекции имеет тип int, то язык C++ гарантирует, что в очередь можно поместить либо значение типа int, либо значение, преобразуемое в такой тип. Это подходит, если предстоит работа с очередями объектов только типа int. Если же класс Queue должен поддерживать также коллекции объектов типа double, char, комплексные числа или строки, подобная реализация оказывается слишком ограничительной.

Конечно, эту проблему можно решить, создав копию класса Queue для работы с типом double, затем для работы с комплексными числами, затем со строками и т.д. А поскольку имена классов перегружать нельзя, каждой реализации придется дать уникальное имя: IntQueue, DoubleQueue, ComplexQueue, StringQueue. При необходимости работать с другим классом придется снова копировать, модифицировать и переименовывать.

Такой метод дублирования кода крайне неудобен. Создание различных уникальных имен для Queue представляет лексическую сложность. Имеются и трудности администрирования: любое изменение общего алгоритма придется вносить в каждую реализацию класса. В общем случае процесс ручной генерации копий для индивидуальных типов никогда не кончается и очень сложен с точки зрения сопровождения.

К счастью, механизм шаблонов C++ позволяет автоматически генерировать такие типы. Шаблон класса можно использовать при создании Queue для очереди объектов любого типа. Определение шаблона этого класса могло бы выглядеть следующим образом:



template <class Type>

class Queue {

public:

Queue();

~Queue();

Type& remove();

void add( const Type & );

bool is_empty();

bool is_full();

private:

// ...

};

Чтобы создать классы Queue, способные хранить целые числа, комплексные числа и строки, программисту достаточно написать:

Queue<int> qi;

Queue<complex<double>> qc;

Queue qs;

Реализация Queue представлена в следующих разделах с целью иллюстрации определения и применения шаблонов классов. В реализации используются две абстракции шаблона:

сам шаблон класса Queue предоставляет описанный выше открытый интерфейс и пару членов: front и back. Очередь реализуется с помощью связанного списка;

шаблон класса QueueItem представляет один узел связанного списка Queue. Каждый помещаемый в очередь элемент сохраняется в объекте QueueItem, который содержит два члена: value и next. Тип value будет различным в каждом экземпляре класса Queue, а next - это всегда указатель на следующий объект QueueItem в очереди.

Прежде чем приступать к детальному изучению реализации этих шаблонов, рассмотрим, как они объявляются и определяются. Вот объявление шаблона класса QueueItem:

template <class T>

class QueueItem;

Как объявление, так и определение шаблона всегда начинаются с ключевого слова template. За ним следует заключенный в угловые скобки список параметров шаблона, разделенных запятыми. Список не бывает пустым. В нем могут быть параметры-типы, представляющие некоторый тип, и параметры-константы, представляющие некоторое константное выражение.

Параметр-тип шаблона состоит из ключевого слова class или typename (в списке параметров они эквивалентны), за которым следует идентификатор. (Ключевое слово typename не поддерживается компиляторами, написанными до принятия стандарта C) Оба ключевых слова обозначают, что последующее имя параметра относится к встроенному или определенному пользователем типу. Например, в приведенном выше определении шаблона QueueItem имеется один параметр-тип T. Допустимым фактическим аргументом для T является любой встроенный или определенный пользователем тип, такой, как int, double, char*, complex или string.

У шаблона класса может быть несколько параметров-типов:

template <class T1, class T2, class T3>

class Container;

Однако ключевое слово class или typename должно предшествовать каждому. Следующее объявление ошибочно:



// ошибка: должно быть <typename T, class U> или

// <typename T, typename U>

template <typename T, U>

class collection;

Объявленный параметр-тип служит спецификатором типа в оставшейся части определения шаблона и употребляется точно так же, как любой встроенный или определенный пользователем тип в обычном определении класса. Например, параметр-тип можно использовать для объявления данных и функций-членов, членов вложенных классов и т.д.

Не являющийся типом параметр шаблона представляет собой обычное объявление. Он показывает, что следующее за ним имя - это потенциальное значение, употребляемое в определении шаблона в качестве константы. Так, шаблон класса Buffer может иметь параметр-тип, представляющий типы элементов, хранящихся в буфере, и параметр-константу, содержащий его размер:

template <class Type, int size>

class Buffer;

За списком параметров шаблона следует определение или объявление класса. Шаблон определяется так же, как обычный класс, но с указанием параметров:

template <class Type>

class QueueItem {

public:

// ...

private:

// Type представляет тип члена

Type item;

QueueItem *next;

};

В этом примере Type используется для обозначения типа члена item. По ходу выполнения программы вместо Type могут быть подставлены различные встроенные или определенные пользователем типы. Такой процесс подстановки называется конкретизацией шаблона.

Имя параметра шаблона можно употреблять после его объявления и до конца объявления или определения шаблона. Если в глобальной области видимости объявлена переменная с таким же именем, как у параметра шаблона, то это имя будет скрыто. В следующем примере тип item равен не double, а типу параметра:

typedef double Type;

template <class Type>

class QueueItem {

public:

// ...

private:

// тип Item - не double

Type item;

QueueItem *next;

};

Член класса внутри определения шаблона не может быть одноименным его параметру:

template >class Type>

class QueueItem {

public:

// ...

private:

// ошибка: член не может иметь то же имя, что и

// параметр шаблона Type

typedef double Type;

Type item;

QueueItem *next;

};

Имя параметра шаблона может встречаться в списке только один раз. Поэтому следующее объявление компилятор помечает как ошибку:

// ошибка: неправильное использование имени параметра шаблона Type

template <class Type, class Type>

class container;

Такое имя разрешается повторно использовать в объявлениях или определениях других шаблонов:

// правильно: повторное использование имени Type в разных шаблонах

template <class Type>

class QueueItem;

template

class Queue;

Имена параметров в опережающем объявлении и последующем определении одного и того же шаблона не обязаны совпадать. Например, все эти объявления QueueItem относятся к одному шаблону класса:

// все три объявления QueueItem

// относятся к одному и тому же шаблону класса

// объявления шаблона

template <class T> class QueueItem;

template <class U> class QueueItem;

// фактическое определение шаблона

template <class Type>

class QueueItem { ... };

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

template <class Type, size = 1024>

class Buffer;

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

template <class Type, size = 1024>

class Buffer;

// правильно: рассматриваются аргументы по умолчанию из обоих объявлений

template <class Type=string, int size>

class Buffer;

(Отметим, что аргументы по умолчанию для параметров шаблонов не поддерживаются в компиляторах, реализованных до принятия стандарта C++. Чтобы компилировались большинством современных компиляторов, мы не использовали такие аргументы.)

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

template <class Type>

class QueueItem {

public:

QueueItem( const Type & );

private:

Type item;

QueueItem *next;

};

Обратите внимание, что каждое появление имени QueueItem в определении шаблона - это сокращенная запись для

QueueItem<Type>

Такую сокращенную нотацию можно употреблять только внутри определения QueueItem (и, как мы покажем в следующих разделах, в определениях его членов, которые находятся вне определения шаблона класса). Если QueueItem применяется как спецификатор типа в определении какого-либо другого шаблона, то необходимо задавать полный список параметров. В следующем примере шаблон класса используется в определении шаблона функции display. Здесь за именем шаблона класса QueueItem должны идти параметры, т.е. QueueItem<Type>.

template <class Type>

void display( QueueItem<Type> &qi )

{

QueueItem<Type> *pqi = &qi;

// ...

}

3.2 Определения шаблонов классов Queue и QueueItem

Ниже представлено определение шаблона класса Queue. Оно помещено в заголовочный файл Queue.h вместе с определением шаблона QueueItem:

#ifndef QUEUE_H

#define QUEUE_H

// объявление QueueItem

template <class T> class QueueItem;

template <class Type>

class Queue {

public:

Queue() : front( 0 ), back ( 0 ) { }

~Queue();

Type& remove();

void add( const Type & );

bool is_empty() const {

return front == 0;

}

private:

QueueItem<Type&lgt; *front;

QueueItem<Type> *back;

};

#endif

При использовании имени Queue внутри определения шаблона класса Queue список параметров <Type> можно опускать. Однако пропуск списка параметров шаблона QueueItem в определении шаблона Queue недопустим. Так, объявление члена front является ошибкой:

template <class Type>

class Queue {

public:

// ...

private:

// ошибка: список параметров для QueueItem неизвестен

QueueItem<Type> *front;

}

3.3 Аргументы шаблона для параметров-констант

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



template <int hi, int wid>

class Screen {

public:

Screen() : _height( hi ), _width( wid ), _cursor ( 0 ),

_screen( hi * wid, '#' )

{ }

// ...

private:

string_screen;

string::size_type _cursor;

short _height;

short _width;

};

typedef Screen<24,80> termScreen;

termScreen hp2621;

Screen<8,24> ancientScreen;

Выражение, с которым связан параметр, не являющийся типом, должно быть константным, т.е. вычисляемым во время компиляции. В примере выше typedef termScreen ссылается на экземпляр шаблона Screen<24,80>, где аргумент шаблона для hi равен 24, а для wid - 80. В обоих случаях аргумент - это константное выражение.

Однако для шаблона BufPtr конкретизация приводит к ошибке, так как значение указателя, получающееся при вызове оператора new(), становится известно только во время выполнения:

template <int *ptr> class BufPtr { ... };

// ошибка: аргумент шаблона нельзя вычислить во время компиляции

BufPtr< new int[24] > bp;

Не является константным выражением и значение неконстантного объекта. Его нельзя использовать в качестве аргумента для параметра-константы шаблона. Однако адрес любого объекта в области видимости пространства имен, в отличие от адреса локального объекта, является константным выражением (даже если спецификатор const отсутствует), поэтому его можно применять в качестве аргумента для параметра-константы. Константным выражением будет и значение оператора sizeof:

template <int size> Buf { ... };

template <int *ptr> class BufPtr { ... };

int size_val = 1024;

const int c_size_val = 1024;

Buf< 1024 > buf0; // правильно

Buf< c_size_val > buf1; // правильно

Buf< sizeof(size_val) > buf2; // правильно: sizeof(int)

BufPtr< &size_val > bp0; // правильно

// ошибка: нельзя вычислить во время компиляции

Buf<< size_val > buf3;

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

template < class Type, int size >

class FixedArray {

public:

FixedArray( Type *ar ) : count( size )

{

for ( int ix = 0; ix < size; ++ix )

array[ ix ] = ar[ ix ];

}

private:

Type array[ size ];

int count;

};

int ia[4] = { 0, 1, 2, 3 };

FixedArray< int, sizeof( is ) / sizeof( int ) > iA{ ia );

Выражения с одинаковыми значениями считаются эквивалентными аргументами для параметров-констант шаблона. Так, все три экземпляра Screen ссылаются на один и тот же конкретизированный из шаблона класс Screen<24,80>:

const int width = 24;

const int height = 80;

// все это Screen< 24, 80 >

Screen< 2*12, 40*2 > scr0;

Screen< 6+6+6+6, 20*2 + 40 > scr1;

Screen< width, height > scr2;

Между типом аргумента шаблона и типом параметра-константы допустимы некоторые преобразования. Их множество является подмножеством преобразований, допустимых для аргументов функции:

1. трансформации l-значений, включающие преобразование l-значения в r-значение, массива в указатель и функции в указатель:

template <int *ptr> class BufPtr { ... };

int array[10];

BufPtr< array > bpObj; // преобразование массива в указатель

2. преобразования квалификаторов:

template class Ptr { ... };

int iObj;

Ptr< &iObj > pObj; // преобразование из int* в const int*

3. расширения типов:

template <int hi, int wid> class Screen { ... };

const short shi = 40;

const short swi = 132;

Screen< shi, swi > bpObj2; // расширения типа short до int

4. преобразования целых типов:

template <unsigned int size> Buf{ ... };

Buf< 1024 > bpObj; // преобразование из int в unsigned int

Рассмотрим следующие объявления:

extern void foo( char * );

extern void bar( void * );

typedef void (*PFV)( void * );

const unsigned int x = 1024;

template <class Type,

unsigned int size,

PFV handler> class Array { ... };

Array<int, 1024U, bar> a0; // правильно: преобразование не нужно

Array<int, 1024U, foo> a1; // ошибка: foo != PFV

Array<int, 1024, bar> a2; // правильно: 1024 преобразуется в unsigned int

Array<int, 1024, bar> a3; // ошибка: foo != PFV

Array<int, x, bar> a4; // правильно: преобразование не нужно

Array<int, x, foo> a5; // ошибка: foo != PFV

Объекты a0 и a4 класса Array определены правильно, так как аргументы шаблона точно соответствуют типам параметров. Объект a2 также определен правильно, потому что аргумент 1024 типа int приводится к типу unsigned int параметра-константы size с помощью преобразования целых типов. Объявления a1, a3 и a5 ошибочны, так как не существует преобразования между любыми двумя типами функций.

Приведение значения 0 целого типа к типу указателя недопустимо:

template <int *ptr>

class BufPtr { ... };

// ошибка: 0 имеет тип int

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

BufPtr< 0 > nil;

3.4 Конкретизация шаблона класса

В определении шаблона указывается, как следует строить индивидуальные классы, если заданы один или более фактических типов или значений. По шаблону Queue автоматически генерируются экземпляры классов Queue с разными типами элементов. Например, если написать:

Queue<int> qi;

то из обобщенного определения шаблона автоматически создается класс Queue для объектов типа int.

Генерация конкретного класса из обобщенного определения шаблона называется конкретизацией шаблона. При такой конкретизации Queue для объектов типа int каждое вхождение параметра Type в определении шаблона заменяется на int, так что определение класса Queue принимает вид:

template <class int>

class Queue {

public:

Queue() : front( 0 ), back ( 0 ) { }

~Queue();

int& remove();

void add( const int & );

bool is_empty() const {

return front == 0;

}

private:

QueueItem<int> *front;

QueueItem<int> *back;

};

Чтобы создать класс Queue для объектов типа string, надо написать:

Queue<string> qs;

При этом каждое вхождение Type в определении шаблона будет заменено на string. Объекты qi и qs являются объектами автоматически созданных классов.

Каждый конкретизированный по одному и тому же шаблону экземпляр класса совершенно не зависит от всех остальных. Так, у Queue для типа int нет никаких прав доступа к неоткрытым членам того же класса для типа string.

Конкретизированный экземпляр шаблона будет иметь соответственно имя Queue<int> или Queue<string>. Части <int> и <string>, следующие за именем Queue, называются фактическими аргументами шаблона. Они должны быть заключены в угловые скобки и отделяться друг от друга запятыми. В имени конкретизируемого шаблона аргументы всегда должны задаваться явно. В отличие от аргументов шаблона функции, аргументы шаблона класса никогда не выводятся из контекста:

Queue qs; // ошибка: как конкретизируется шаблон?

Конкретизированный шаблон класса Queue можно использовать в программе всюду, где допустимо употребление типа обычного класса:

// типы возвращаемого значения и обоих параметров конкретизированы из

// шаблона класса Queue

extern Queue< complex<double>>

foo( Queue< complex<double>> &, Queue complex<double>> & );

// указатель на функцию-член класса, конкретизированного из шаблона Queue

bool (Queue<double>::*pmf)() = 0;

// явное приведение 0 к указателю на экземпляр Queue

Queue<char*> *pqc = static_cast< Queue<char*>* > ( 0 );

Объекты типа класса, конкретизированного по шаблону Queue, объявляются и используются так же, как объекты обычных классов:

extern Queue<double>eqd;

Queue<int&lgt; *pqi = new Queue<int>;

Queue<int> aqi[1024];

int main() {

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

// объявление шаблона функции

template <class Type>

void bar( Queue<Type> &, // ссылается на обобщенный шаблон

Queue<double> & // ссылается на конкретизированный шаблон

)

Однако вне такого определения употребляются только конкретизированные экземпляры. Например, в теле обычной функции всегда надо задавать фактические аргументы шаблона Queue:

void foo( Queue<int> &qi )

{

Queue<int> *pq = &qi;

// ...

}

Шаблон класса конкретизируется только тогда, когда имя полученного экземпляра употребляется в контексте, где требуется определение шаблона. Не всегда определение класса должно быть известно. Например, перед объявлением указателей и ссылок на класс его знать необязательно:

class Matrix;

Matrix *pm; // правильно: определение класса Matrix знать необязательно

void inverse( Matrix & ); // тоже правильно

Поэтому объявление указателей и ссылок на конкретизированный шаблон класса не приводит к его конкретизации. (Отметим, что в некоторых компиляторах, написанных до принятия стандарта C++, шаблон конкретизируется при первом упоминании имени конкретизированного класса в тексте программы.) Так, в функции foo() объявляются указатель и ссылка на Queue, но это не вызывает конкретизации шаблона Queue:

// Queue<int> не конкретизируется при таком использовании в foo()

void foo( Queue<int> &qi )

{

Queue<int> *pqi = &qi;

// ...

}

Определение класса необходимо знать, когда определяется объект этого типа. В следующем примере определение obj1 ошибочно: чтобы выделить для него память, компилятору необходимо знать размер класса Matrix:

class Matrix;

Matrix obj1; // ошибка: класс Matrix не определен

class Matrix { ... };

Matrix obj2; // правильно

Таким образом, конкретизация происходит тогда, когда определяется объект класса, конкретизированного по этому шаблону. В следующем примере определение объекта qi приводит к конкретизации шаблона Queue:

Queue<int> qi; // конкретизируется Queue<int>

Определение Queue<int> становится известно компилятору именно в этой точке, которая называется точкой конкретизации данного класса.

Если имеется указатель или ссылка на конкретизированный шаблон, то конкретизация также производится в момент обращения к объекту, на который они ссылаются. В определенной выше функции foo() класс Queue конкретизируется в следующих случаях: когда разыменовывается указатель pqi, когда ссылка qi используется для получения значения именуемого объекта и когда pqi или qi употребляются для доступа к членам или функциям-членам этого класса:

void foo( Queue<int> &qi )

{

Queue<int> *pqi = &qi;

// Queue конкретизируется в результате вызова функции-члена

pqi->add( 255 );

// ...

}

Определение Queue<int> становится известным компилятору еще до вызова функции-члена add() из foo().

Напомним, что в определении шаблона класса Queue есть также ссылка на шаблон QueueItem:

template <class Type>

class Queue {

public:

// ...

private:

QueueItem<Type> *front;

QueueItem<Type> *back;

};



При конкретизации Queue типом int члены front и back становятся указателями на QueueItem. Следовательно, конкретизированный экземпляр Queue<int> ссылается на экземпляр QueueItem, конкретизированный типом int. Но поскольку соответствующие члены являются указателями, то QueueItem<int> конкретизируется лишь в момент их разыменования в функциях-членах класса Queue<int>.

Наш класс QueueItem служит вспомогательным средством для реализации класса Queue и не будет непосредственно употребляться в вызывающей программе. Поэтому пользовательская программа способна манипулировать только объектами Queue. Конкретизация шаблона QueueItem происходит лишь в момент конкретизации шаблона класса Queue или его членов. (В следующих разделах мы рассмотрим конкретизации членов шаблона класса.)

В зависимости от типов, которыми может конкретизироваться шаблон, при его определении надо учитывать некоторые нюансы. Почему, например, следующее определение конструктора класса QueueItem не подходит для конкретизации общего вида?

template <class Type>

class кретизация производится для объемного типа (скажем, Matrix), то накладные расходы, вызванные неправильным выбором на этапе проектирования, становятся неприемлемыми. (В разделе 7.3 обсуждались вопросы производительности, связанные с передачей параметров по значению и по ссылке.) Поэтому аргумент конструктора объявляется как ссылка на константный тип:

QueueItem( const Type & );



Следующее определение приемлемо, если у типа, для которого конкретизируется QueueItem, нет ассоциированного конструктора:

template <class Type>

class QueueItem {

// ...

public:

// потенциально неэффективно

QueueItem( const Type &t ) {

item = t; next = 0;

}

};

Если аргументом шаблона является тип класса с конструктором (например, string), то item инициализируется дважды! Конструктор по умолчанию string вызывается для инициализации item перед выполнением тела конструктора QueueItem. Затем для созданного объекта item производится почленное присваивание. Избежать такого можно с помощью явной инициализации item в списке инициализации членов внутри определения конструктора QueueItem:

template <class Type>

class QueueItem {

// ...

public:

// item инициализируется в списке инициализации членов конструктора

QueueItem( const Type &t )

: item(t) { next = 0; }

};

3.5 Функции-члены шаблонов классов

Как и для обычных классов, функция-член шаблона класса может быть определена либо внутри определения шаблона (и тогда называется встроенной), либо вне его. Мы уже встречались со встроенными функциями-членами при рассмотрении шаблона Queue. Например, конструктор Queue является встроенным, так как определен внутри определения шаблона класса:

template < class Type>

class Queue {

// ...

public:

// встроенный конструктор

Queue() : front( 0 ), back( 0 ) { }

// ...

};

При определении функции-члена шаблона вне определения самого шаблона следует применять специальный синтаксис для обозначения того, членом какого именно шаблона является функция. Определению функции-члена должно предшествовать ключевое слово template, за которым следуют параметры шаблона. Так, конструктор Queue можно определить следующим образом:

template < class Type>

class Queue {

public:

Queue();

private:

// ...

};

template < class Type>

inline Queue< Type> ::

Queue( ) { front = back = 0; }

За первым вхождением Queue (перед оператором ::) следует список параметров, показывающий, какому шаблону принадлежит данная функция-член. Второе вхождение Queue в определение конструктора (после оператора ::) содержит имя функции-члена, за которым может следовать список параметров шаблона, хотя это и необязательно. После имени функции идет ее определение;. в нем могут быть ссылки на параметр шаблона Type всюду, где в определении обычной функции использовалось бы имя типа.

Функция-член шаблона класса сама является шаблоном. Стандарт C++ требует, чтобы она конкретизировалась только при вызове либо при взятии ее адреса. (Некоторые более старые компиляторы конкретизируют такие функции одновременно с конкретизацией самого шаблона класса.) При конкретизации функции-члена используется тип того объекта, для которого функция вызвана:

Queue< string> qs;

Объект qs имеет тип Queue< string> . При инициализации объекта этого класса вызывается конструктор Queue<string>. В данном случае аргументом, которым конкретизируется функция-член (конструктор), будет string.

Функция-член шаблона конкретизируется только при реальном использовании в программе (т.е. при вызове или взятии ее адреса). От того, в какой именно момент конкретизируется функция-член, зависит разрешение имен в ее определении и объявление ее специализации



3.6 Функции-члены шаблонов Queue и QueueItem

Чтобы понять, как определяются и используются функции-члены шаблонов классов, продолжим изучение шаблонов Queue и QueueItem:

template < class Type>

class Queue {

public:

Queue() : front( 0 ), back ( 0 ) { }

~Queue();

Type& remove();

void add( const Type & );

bool is_empty() const {

return front == 0;

}

private:

QueueItem< Type> *front;

QueueItem< Type> *back;

};

Деструктор, а также функции-члены remove() и add() определены не в теле шаблона, а вне его. Деструктор Queue опустошает очередь:

template < class Type>

Queue< Type> ::~Queue()

{

while (! is_empty() )

remove();

}



Функция-член Queue< Type> ::add() помещает новый элемент в конец очереди:

template < class Type>

void Queue< Type> ::add( const Type &val )

{

// создать новый объект QueueItem

QueueItem< Type> *pt =

new QueueItem< Type> ( val );

if ( is_empty() )

front = back = pt;

else

{

back-> next = pt;

back = pt;

}

}

Функция-член Queue< Type> ::remove() возвращает значение элемента, находящегося в начале очереди, и удаляет сам элемент.

#include < iostream>

#include < cstdlib>

template < class Type>

Type Queue< Type> ::remove()

{

if ( is_empty() )

{

cerr < < "remove() вызвана для пустой очереди\n";

exit( -1 );

}

QueueItem< Type> *pt = front;

front = front-> next;

Type retval = pt-> item;

delete pt;

return retval;

}

Мы поместили определения функций-членов в заголовочный файл Queue.h, включив его в каждый файл, где возможны конкретизации функций. (Обоснование этого решения, а также рассмотрение более общих вопросов, касающихся модели компиляции шаблонов, мы отложим до раздела 16.8.)

В следующей программе иллюстрируется использование и конкретизация функции-члена шаблона Queue:

#include < iostream>

#include "Queue.h"

int main()

{

// конкретизируется класс Queue< int>

// оператор new требует, чтобы Queue< int> был определен

Queue< int> *p_qi = new Queue< int> ;

int ival;

for ( ival = 0; ival < 10; ++ival )

// конкретизируется функция-член add()

p_qi-> add( ival );

int err_cnt = 0;

for ( ival = 0; ival < 10; ++ival ) {

// конкретизируется функция-член remove()

int qval = p_qi-> remove();

if ( ival != qval ) err_cnt++;

}

if ( !err_cnt )

cout < < "!! queue executed ok\n";

else cerr << "?? queue errors: " < < err_cnt << endl;

return 0;

}

После компиляции и запуска программа выводит следующую строку:

!! queue executed ok

3.7 Объявления друзей в шаблонах классов

обычный (не шаблонный) дружественный класс или дружественная функция. В следующем примере функция foo(), функция-член bar() и класс foobar объявлены друзьями всех конкретизаций шаблона QueueItem:

<pre>class Foo {

void bar();

};

template <class T>

class QueueItem {

friend class foobar;

friend void foo();

friend void Foo::bar();

// ...

};

Ни класс foobar, ни функцию foo() не обязательно объявлять или определять в глобальной области видимости перед объявлением их друзьями шаблона QueueItem.

Однако перед тем как объявить другом какой-либо из членов класса Foo, необходимо определить его. Напомним, что член класса может быть введен в область видимости только через определение объемлющего класса. QueueItem не может ссылаться на Foo::bar(), пока не будет найдено определение Foo;

связанный дружественный шаблон класса или функции. В следующем примере определено взаимно однозначное соответствие между классами, конкретизированными по шаблону QueueItem, и их друзьями - также конкретизациями шаблонов. Для каждого класса, конкретизированного по шаблону QueueItem, ассоциированные конкретизации foobar, foo() и Queue::bar() являются друзьями.

template <class Type>

class foobar { ... };

template <class Type>

void foo( QueueItem<Type>);

template <class Type>

class Queue {

void bar();

// ...

};

template <class Type>

class QueueItem {

friend class foobar<Type>;

friend void foo<Type>( QueueItem<Type> );

friend void Queue<Type>::bar();

// ...

};



Прежде чем шаблон класса можно будет использовать в объявлениях друзей, он сам должен быть объявлен или определен. В нашем примере шаблоны классов foobar и Queue, а также шаблон функции foo() следует объявить до того, как они объявлены друзьями в QueueItem.

Синтаксис, использованный для объявления foo() другом, может показаться странным:

friend void foo<Type>( QueueItem<Type> );

За именем функции следует список явных аргументов шаблона: foo<Type>. Такой синтаксис показывает, что в качестве друга объявляется конкретизированный шаблон функции foo(). Если бы список явных аргументов был опущен:

friend void foo( QueueItem<Type> );

то компилятор интерпретировал бы объявление как относящееся к обычной функции (а не к шаблону), у которой тип параметра - это экземпляр шаблона QueueItem. Как отмечалось в разделе 10.6, шаблон функции и одноименная обычная функция могут сосуществовать, и присутствие объявления такого шаблона перед определением класса QueueItem не вынуждает компилятор соотнести объявление друга именно с ним. Для того, чтобы соотнесение было верным, в конкретизированном шаблоне функции необходимо указать список явных аргументов;

несвязанный дружественный шаблон класса или функции. В следующем примере имеется отображение один-ко-многим между конкретизациями шаблона класса QueueItem и его друзьями. Для каждой конкретизации типа QueueItem все конкретизации foobar, foo() и Queue::bar() являются друзьями:



template <class Type>

class QueueItem {

template <class T>

friend class foobar;

template <class T>

friend void foo( QueueItem<T> );

template <class T>

friend class Queue<T>::bar();

// ...

};

Следует отметить, что этот вид объявлений друзей в шаблоне класса не поддерживается компиляторами, написанными до принятия стандарта C++.

3.8 Объявления друзей в шаблонах Queue и QueueItem

Поскольку QueueItem не предназначен для непосредственного использования в вызывающей программе, то объявление конструктора этого класса помещено в закрытую секцию шаблона. Теперь класс Queue необходимо объявить другом QueueItem, чтобы можно было создавать и манипулировать объектами последнего.

Существует два способа объявить шаблон класса другом. Первый заключается в том, чтобы объявить любой экземпляр Queue другом любого экземпляра QueueItem:

template <class Type>QueueItem,

конкретизированного типом complex<double>. Queue должен быть другом только для класса QueueItem. Таким образом, нам нужно взаимно однозначное соответствие между экземплярами Queue и QueueItem, конкретизированными одинаковыми типами. Чтобы добиться этого, применим второй метод объявления друзей:

template <class Type>

class QueueItem {

// для любого экземпляра QueueItem другом является

// только конкретизированный тем же типом экземпляр Queue

friend class Queue<Type>;

// ...

};

Данное объявление говорит о том, что для любой конкретизации QueueItem некоторым типом экземпляр Queue, конкретизированный тем же типом, является другом. Так, экземпляр Queue, конкретизированный типом int, будет другом экземпляра QueueItem, тоже конкретизированного типом int. Но для экземпляров QueueItem, конкретизированных типами complex<double> или string, этот экземпляр Queue другом не будет.

В любой точке программы у пользователю может понадобиться распечатать содержимое объекта Queue. Такая возможность предоставляется с помощью перегруженного оператора вывода. Этот оператор должен быть объявлен другом шаблона Queue, так как ему необходим доступ к закрытым членам класса. Какой же будет его сигнатура?

// как задать аргумент типа Queue?

ostream& operator<<( ostream &, ??? );

Поскольку Queue - это шаблон класса, то в имени конкретизированного экземпляра должен быть задан полный список аргументов:



ostream& operator<<( ostream &, const Queue<int> & );

Так мы определили оператор вывода для класса, конкретизированного из шаблона Queue типом int. Но что, если Queue - это очередь элементов типа string?

ostream& operator<<( ostream &, const Queue<string> & );

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

ostream& operator<<( ostream &, const Queue<Type> & );

Однако из этого перегруженного оператора вывода придется сделать шаблон функции:

template <class Type> ostream&

operator<<( ostream &, const Queue<Type> & );

Теперь всякий раз, когда оператору ostream передается конкретизированный экземпляр Queue, конкретизируется и вызывается шаблон функции. Вот одна из возможных реализаций оператора вывода в виде такого шаблона:

template <class Type>

ostream& operator<<( ostream &os, const Queue<Type> &q )

{

os << "< ";

QueueItem<Type> *p;

for ( p = q.front; p; p = p-> next )

os << *p << " ";

os << " > ";

return os;

}

Если очередь объектов типа int содержит значения 3, 5, 8, 13, то распечатка ее содержимого с помощью такого оператора дает < 3 5 8 13 >>

Обратите внимание, что оператор вывода обращается к закрытому члену front класса Queue. Поэтому оператор необходимо объявить другом Queue:

template <class Type>

class Queue {

friend ostream&

operator<<( ostream &, const Queue<Type> & );

// ...

};

Здесь, как и при объявлении друга в шаблоне класса Queue, создается взаимно однозначное соответствие между конкретизациями Queue и оператора operator<<().

Распечатка элементов Queue производится оператором вывода operator<<() класса QueueItem:

os << *p;

Этот оператор также должен быть реализован в виде шаблона функции; тогда можно быть уверенным, что в нужный момент будет конкретизирован подходящий экземпляр:

template <class Type>

ostream& operator<< ( ostream &os, const QueueItem<Type> &qi )

{

os << qi.item;

return os;

}

Поскольку здесь имеется обращение к закрытому члену item класса QueueItem, оператор следует объявить другом шаблона QueueItem. Это делается следующим образом:

template <class Type>

class QueueItem {

friend class Queue<Type>;

friend ostream&

operator<< ( ostream &, const QueueItem<Type> & );

// ...

};

Оператор вывода класса QueueItem полагается на то, что item умеет распечатывать себя:

Следующая программа демонстрирует конкретизацию и использование функций-друзей шаблонов классов Queue и QueueItem:

#include <iostream>

#include "Queue.h"

int main() {

Queue<int> qi;

// конкретизируются оба экземпляра

// ostream& operator<< (ostream &os, const Queue<int>&)

// ostream& operator<< (ostream &os, const QueueItem<int> &)

cout << qi << endl;

int ival;

for ( ival = 0; ival < 10; ++ival )

qi.add( ival );

cout << qi << endl;

int err_cnt = 0;

for ( ival = 0; ival < 10; ++ival ) {

int qval = qi.remove();

if ( ival != qval ) err_cnt++;

}

cout << qi << endl;

if ( !err_cnt )

cout << "!! queue executed ok\n";

else cout << "?? queue errors: " << err_cnt << endl;

return 0;

}

После компиляции и запуска программа выдает результат:

< >

< 0 1 2 3 4 5 6 7 8 9 >

< >

!! queue executed ok

3.9 Статические члены шаблонов класса

В шаблоне класса могут быть объявлены статические данные-члены. Каждый конкретизированный экземпляр имеет собственный набор таких членов. Рассмотрим операторы new() и delete() для шаблона QueueItem. В класс QueueItem нужно добавить два статических члена:

static QueueItem<Type> *free_list;

static const unsigned QueueItem_chunk;

Модифицированное определение шаблона QueueItem выглядит так:

#include <cstddef>

template <class Type>

class QueueItem {

// ...

private: