void *operator new( size_t );

void operator delete( void *, size_t );

// ...

static QueueItem *free_list;

static const unsigned QueueItem_chunk;

// ...

};

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

Оператор new() можно реализовать таким образом:

template <class Type> void*

QueueItem<Type>::operator new( size_t size )

{

QueueItem<Type> *p;

if ( ! free_list )

{

size_t chunk = QueueItem_chunk * size;

free_list = p =

reinterpret_cast< QueueItem< Type> * >

( new char[chunk] );

for ( ; p != &free_list[ QueueItem_chunk - 1 ]; ++p )

p-> next = p + 1;

p-> next = 0;

}

p = free_list;

free_list = free_list-> next;

return p;

}

А реализация оператора delete() выглядит так:

template class <Type>

void QueueItem<Type> ::

operator delete( void *p, size_t )

{

static_cast< QueueItem<Type> * > ( p )-> next = free_list;

free_list = static_cast< QueueItem<Type> * > ( p );

}

Теперь остается инициализировать статические члены free_list и QueueItem_chunk. Вот шаблон для определения статических данных-членов:

/* для каждой конкретизации QueueItem сгенерировать

* соответствующий free_list и инициализировать его нулем

*/

template <class T>

QueueItem<T> *QueueItem<T>::free_list = 0;

* для каждой конкретизации QueueItem сгенерировать

* соответствующий QueueItem_chunk и инициализировать его значением 24

*/

template <class T>

const unsigned int

QueueItem<T>::QueueItem_chunk = 24;

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

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

// ошибка: QueueItem - это не реальный конкретизированный экземпляр

int ival0 = QueueItem::QueueItem_chunk;

int ival1 = QueueItem<string>::QueueItem_chunk; // правильно

int ival2 = QueueItem<int>::QueueItem_chunk;// правильно



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

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

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

Семантика исходной реализации при этом сохраняется, но отношение между шаблонами QueueItem и Queue моделируется более элегантно.

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

template <class Type>

class Queue:

// ...

private:

class QueueItem {

public:

QueueItem( Type val )

: item( val ), next( 0 ) { ... }

Type item;

QueueItem *next;

};

// поскольку QueueItem - вложенный тип,

// а не шаблон, определенный вне Queue,

// то аргумент шаблона <Type> после QueueItem можно опустить

QueueItem *front, *back;

// ...

};

При каждой конкретизации Queue создается также класс QueueItem с подходящим аргументом для Type. Между конкретизациями шаблонов QueueItem и Queue имеется взаимно однозначное соответствие.

Вложенный в шаблон класс конкретизируется только в том случае, если он используется в контексте, где требуется полный тип класса. В разделе 16.2 мы упоминали, что конкретизация шаблона класса Queue типом int не означает автоматической конкретизации и класса QueueItem<int>. Члены front и back - это указатели на QueueItem<int>, а если объявлены только указатели на некоторый тип, то конкретизировать соответствующий класс не обязательно, хотя QueueItem вложен в шаблон класса Queue. QueueItem<int> конкретизируется только тогда, когда указатели front или back разыменовываются в функциях-членах класса Queue<int>.

Внутри шаблона класса можно также объявлять перечисления и определять типы (с помощью typedef):

template <class Type, int size>

class Buffer:

public:

enum Buf_vals { last = size-1, Buf_size };

typedef Type BufType;

BufType array[ size ];

// ...

}

Вместо того чтобы явно включать член Buf_size, в шаблоне класса Buffer объявляется перечисление с двумя элементами, которые инициализируются значением параметра шаблона. Например, объявление

Buffer<int, 512> small_buf;

устанавливает Buf_size в 512, а last - в 511. Аналогично

Buffer<int, 1024> medium_buf;

устанавливает Buf_size в 1024, а last - в 1023.

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

// ошибка: какая конкретизация Buffer?

Buffer::Buf_vals bfv0;

Buffer<int,512>::Buf_vals bfv1; // правильно

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

template <class T> class Q {

public:

enum QA { empty, full }; // не зависит от параметров

QA status;

// ...

};

#include <iostream>

int main() {

Q<double> qd;

Q<int> qi;

qd.status = Q::empty; // ошибка: какая конкретизация Q?

qd.status = Q<double> ::empty; // правильно

int val1 = Q<double> ::empty;

int val2 = Q<int> ::empty;

if ( val1 != val2 )

cerr < <"ошибка реализации!" < <endl;

return 0;

}

Во всех конкретизациях Q значения empty одинаковы, но при ссылке на empty необходимо указывать, какому именно экземпляру Q принадлежит перечисление.

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

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



template < class T>

class Queue {

private:

// шаблон класса-члена

template < class Type> class CL

{

Type member;

T mem;

};

// ...

public:

// шаблон функции-члена

template < class Iter>

void assign( Iter first, Iter last )

{

while ( ! is_empty() )

remove();// вызывается Queue< T> ::remove()

for ( ; first != last; ++first )

add( *first ); // вызывается Queue< T> ::add( const T & )

}

}

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

Объявление шаблона-члена имеет собственные параметры. Например, у шаблона класса CL есть параметр Type, а у шаблона функции assign() - параметр Iter. Помимо этого, в определении шаблона-члена могут использоваться параметры объемлющего шаблона класса. Например, у шаблона CL есть член типа T, представляющего параметр включающего шаблона Queue.

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

Queue<int>::CL<char>

Queue<int> ::CL<string>

и вложенные функции:

void Queue<int> ::assign( int *, int * )

void Queue<int> ::assign( vector<int> ::iterator,

vector<int> ::iterator )

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

Шаблон-член конкретизируется при его использовании в программе. Например, assign() конкретизируется в момент обращения к ней из main():

int main()

{

// конкретизация Queue<int>

Queue<int> qi;

// конкретизация Queue<int>::assign( int *, int * )

int ai[4] = { 0, 3, 6, 9 };

qi.assign( ai, ai + 4 );

// конкретизация Queue<int> ::assign( vector<int> ::iterator,

// vector<int> ::iterator )

vector<int> vi( ai, ai + 4 );

qi.assign( vi.begin(), vi.end() );

}

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

В функции main() шаблон-член assign() сначала конкретизируется типом int*, что позволяет поместить в qi содержимое массива элементов типа int. Затем шаблон-член конкретизируется типом vector<int>::iterator - это дает возможность поместить в очередь qi содержимое вектора элементов типа int. Контейнер, содержимое которого помещается в очередь, не обязательно должен состоять из элементов типа int. Разрешен любой тип, который приводится к int. Чтобы понять, почему это так, еще раз посмотрим на определение assign():

template <class Iter>

void assign( Iter first, Iter last )

{

// удалить все элементы из очереди

for ( ; first != last; ++first )

add( *first );

}

Вызываемая из assign() функция add() - это функция-член Queue<Type>::add(). Если Queue конкретизируется типом int, то у add() будет следующий прототип:

void Queue<int>::add( const int &val );

Аргумент *first должен иметь тип int либо тип, которым можно инициализировать параметр-ссылку на const int. Преобразования типов допустимы. Например, если воспользоваться классом SmallInt, то содержимое контейнера, в котором хранятся элементы типа SmallInt, с помощью шаблона-члена assign() помещается в очередь типа Queue<int>. Это возможно потому, что в классе SmallInt имеется конвертер для приведения SmallInt к int:

class SmallInt {

public:

SmallInt( int ival = 0 ) : value( ival ) { }

// конвертер: SmallInt ==> int

operator int() { return value; }

// ...

private:

int value;

};

int main()

{

// конкретизация Queue<int>

Queue<int> qi;

vector<SmallInt> vsi;

// заполнить вектор

// конкретизация

// Queue<int> ::assign( vector<SmallInt> ::iterator,

// vector<SmallInt> ::iterator )

qi.assign( vsi.begin(), vsi.end() );

list<int*> lpi;

// заполнить список

// ошибка при конкретизации шаблона-члена assign():

// нет преобразования из int* в int

qi.assign( lpi.begin(), lpi.end() );

}

Первая конкретизация assign() правильна, так как существует неявное преобразование из типа SmallInt в тип int и, следовательно, обращение к add() корректно. Вторая же конкретизация ошибочна: объект типа int* не может инициализировать ссылку на тип const int, поэтому вызвать функцию add() невозможно.

Для контейнерных типов из стандартной библиотеки C++ имеется функция assign(), которая ведет себя так же, как функция-шаблон assign() для нашего класса Queue.

Любую функцию-член можно задать в виде шаблона. Это относится, в частности, к конструктору. Например, для шаблона класса Queue его можно определить следующим образом:

template < class T>

class Queue {

// ...

public:

// шаблон-член конструктора

template < class Iter>

Queue( Iter first, Iter last )

: front( 0 ), back( 0 )

{

for ( ; first != last; ++first )

add( * first );

}

};

Такой конструктор позволяет инициализировать очередь содержимым другого контейнера. У контейнерных типов из стандартной библиотеки C++ также есть предназначенные для этой цели конструкторы в виде шаблонов-членов. Кстати, в первом (в данном разделе) определении функции main() использовался конструктор-шаблон для вектора:

vector< int> vi( ai, ai + 4 );

Это определение конкретизирует шаблон конструктора для контейнера vector типом int*, что позволяет инициализировать вектор содержимым массива элементов типа int.

Шаблон-член, как и обычные члены, может быть определен вне определения объемлющего класса или шаблона класса. Так, являющиеся членами шаблон класса CL или шаблон функции assign() могут быть следующим образом определены вне шаблона Queue:

template < class T>

class Queue {

private:

template <class Type> class CL;

// ...

public:

template < class Iter>

void assign( Iter first, Iter last );

// ...

};

template < class T> template < class Type>

class Queue< T> ::CL<Type>

{

Type member;

T mem;

};

template < class T> template < class Iter>

void Queue< T> ::assign( Iter first, Iter last )

{

while ( ! is_empty() )

remove();

for ( ; first != last; ++first )

add( *first );

}

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

template < class T> template < class Iter>

Первый список параметров шаблона template < class T> относится к шаблону класса Queue. Второй - к самому шаблону-члену assign(). Имена параметров не обязаны совпадать с теми, которые указаны внутри определения объемлющего шаблона класса. Приведенная инструкция по-прежнему определяет шаблон-член assign():

template < class TT> template < class IterType>

void Queue< TT> ::assign( IterType first, IterType last )

{ ... }

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

Определение шаблона класса - это лишь предписание для построения бесконечного множества типов классов. Сам по себе шаблон не определяет никакого класса. Например, когда компилятор видит:

template <class Type>

class Queue { ... };

он только сохраняет внутреннее представление Queue. Позже, когда встречается реальное использование класса, конкретизированного по шаблону, скажем:

int main() {

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

}

компилятор конкретизирует тип класса Queue<int>, применяя сохраненное внутреннее представление определения шаблона Queue.

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

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

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

template < class Type>

class Queue;

Queue<int> * global_pi = 0; // правильно: определение класса не нужно

int main() {

// ошибка: необходима конкретизация

// определение шаблона класса должно быть видимо

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

}

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

Функции-члены и статические данные-члены шаблонов классов, а также вложенные в них типы ведут себя почти так же, как сами шаблоны. Определения членов шаблона используются для порождения экземпляров членов в конкретизированном шаблоне. Если компилятор видит:



template < class Type>

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

{ ... }

он сохраняет внутреннее представление Queue< Type>::add(). Позже, когда в программе встречается фактическое употребление этой функции-члена, допустим через объект типа Queue<int>, компилятор конкретизирует Queue<int>::add(const int &), пользуясь таким представлением:

#include "Queue.h "

int main() {

// конкретизация Queue< int>

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

int ival;

// ...

// конкретизация Queue< int>::add( const int & )

p_qi-< add( ival );

// ...

}

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

Чтобы компилятор мог конкретизировать функцию-член или статический член шаблона класса, должно ли определение члена быть видимым в момент конкретизации? Например, должно ли определение функции-члена add() появиться до ее конкретизации типом int в main()? Следует ли помещать определения функций-членов и статических членов шаблонов класса в заголовочные файлы (как мы поступаем с определениями встроенных функций), которые включаются всюду, где применяются их конкретизированные экземпляры? Или конкретизации определения шаблона достаточно для того, чтобы этими членами можно было пользоваться, так что определения членов можно оставлять в файлах с исходными текстами (где обычно располагаются определения невстроенных функций-членов и статических членов)?

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

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

В этой модели мы включаем определения функций-членов и статических членов шаблонов классов в каждый файл, где они конкретизируются. Для встроенных функций-членов, определенных в теле шаблона, это происходит автоматически. В противном случае такое определение следует поместить в один заголовочный файл с определением шаблона класса. Именно этой моделью мы и пользуемся в настоящей книге. Например, определения шаблонов Queue и QueueItem, как и их функций-членов и статических членов, находятся в заголовочном файле Queue.h.

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

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

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

// ---- Queue.h ----

// объявляет Queue как экспортируемый шаблон класса

export template <class Type>

class Queue {

// ...

public:

Type& remove();

void add( const Type & );

// ...

};

// ---- Queue.C ----

// экспортированное определение шаблона класса Queue

// находится в Queue.h

#include "Queue.h"

template <class Type>

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

template <class Type>

Type& Queue<Type>::remove() { ... }

Программа, в которой используется конкретизированная функция-член, должна перед конкретизацией включить заголовочный файл:

// ---- User.C ----

#include "Queue.h"

int main() {

// конкретизация Queue

Queue *p_qi = new Queue;

int ival;

// ...

// правильно: конкретизация Queue::add( const int & )

p_qi->add( ival );

// ...

}

Хотя определение шаблона для функции-члена add() не видно в файле User.C, конкретизированный экземпляр Queue::add(const int &) вызывать оттуда можно. Но для этого шаблон класса необходимо объявить экспортируемым.

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

Чтобы объявить шаблон класса экспортируемым, перед словом template в его определении или объявлении нужно поставить ключевое слово export:



export template <class Type>

class Queue { ... };

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

Отметим, что, хотя шаблон класса объявлен экспортируемым, его собственное определение должно присутствовать в файле User.C. Конкретизация Queue::add() в User.C вводит определение класса, в котором объявлены функции-члены Queue::add() и Queue::remove(). Эти объявления обязаны предшествовать вызову указанных функций. Таким образом, слово export влияет лишь на обработку функций-членов и статических данных-членов.

Экспортируемыми можно объявлять также отдельные члены шаблона. В этом случае ключевое слово export указывается не перед шаблоном класса, а только перед экспортируемыми членами. Например, если автор шаблона класса Queue хочет экспортировать лишь функцию-член Queue::add() (т.е. изъять из заголовочного файла Queue.h только ее определение), то слово export можно указать именно в определении функции-члена add():

// ---- Queue.h ----

template <class Type>

class Queue {

// ...

public:

Type& remove();

void add( const Type & );

// ...

};

// необходимо, так как remove() не экспортируется

template <class Type>

Type& Queue<Type>::remove() { ... }

// ---- Queue.C ----

#include "Queue.h"

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

export template <class Type>

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

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

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

при редактировании связей возникает ошибка, показывающая, что один и тот же член шаблона класса определен несколько раз;

компилятор неоднократно конкретизирует некоторый член одним и тем же множеством аргументов шаблона, что приводит к ошибке повторного определения во время связывания программы;

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

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

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

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

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

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

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

Подобные проблемы, характерные для старых компиляторов, затрудняли использование шаблонов. Чтобы помочь программисту управлять моментом, когда конкретизация происходит, в стандарте C++ введено понятие явного объявления конкретизации, где за ключевым словом template идет слово class и имя конкретизируемого шаблона класса.

В следующем примере явно объявляется конкретизация шаблона Queue<int>, в котором запрашивается конкретизация аргументом int шаблона класса Queue:

#include "Queue.h"

// явное объявление конкретизации

template class Queue<int>;

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

template <class Type>

class Queue;

// ошибка: шаблон Queue и его члены не определены

template class Queue<int>;

Если в некотором исходном файле встречается явное объявление конкретизации, то что произойдет в других файлах, где используется такой же конкретизированный шаблон? Как сказать компилятору, что явное объявление имеется в другом файле и что при употреблении шаблона класса или его членов в этом файле конкретизировать ничего не надо?

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



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

Основу программы составляет циклический двусвязный список, шаблон класса < class CyDoublewayList>, который включает в себя структуру < struct node> являющуюся элементарным элементом этого списка и хранящую в себе массив указателей на элементы, заданные параметром шаблона. Класс разработан таким образом, что может быть использован с любым типом данных хранимых в нём.

Класс < class StringMy> является конткйнерным классом кторый обеспечивает хранение строк текста, каждый такой объект этого класса хранит в себе одну строку. Каждый указатель из массива в структуре < struct node > указывает на одну такую строку располагающуюся в памяти в области динамического обмена.

Класс < class StartMenu > по сути является интерфейсом, обеспечивающим взаимодействие с пользователем. Реализует меню и выводит результат работы на экран.

Схема взаимосвязей классов изображена на рис 2.

Рис 2. Связи объектов



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

Как таковая иерархия классов в программе отсутствует в классическом её понимании.Не применяется наследование, нет классов-потомков и классов-родителей. Взаимосвязи классов отражены на следующей ниже UML-схеме (Рис 3).

Рис 3. UML-схема взаимосвязей классов.

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

Работу программы можно описать следующей UML-схемой.

Рис. 4. UML-схема

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

7.1 Class CyDoublewayList

- шаблон класса (основа всей программы).

Включает в себя:

Переменную < node *head > указатель на голову списка,

Переменную < node *tail > указатель на хвост списка,

Переменную < int lsize > для хранения размера списка в элементах

Два конструктора,

< CyDoublewayList(void) > - конструктор по умолчанию.

< CyDoublewayList(int size) > - конструктор с заданным количеством пустых узлов.

Деструктор,

< ~CyDoublewayList(void) > - обеспечивающий очистку памяти в процессе удаления объекта.

Методы,

< node* AddNode(int count = 1) > - добавляет в список заданное количество узлов ( по умолчанию один) и возвращает указатель на первый добавленный чтобы при необходимости с него начть заполнение списка.



Рис.5. Принцип работы функции AddNode()

< node* GetLogNode(int num) > - возвращает указатель на элемент списка в котором находится запись с логическим номером < int num >, либо NULL если номер превышает общее количество ячеек в списке:

…

if(nodenum > lsize){

std::cerr << "\nОШИБКА такого узла нет\n";

return NULL;

}

…

< void GetLogNumRecord(int num) > - выводит на экран запись с заданным логическим номером < int num >:

…

node* tmp = head;

for(int i=1; i<nodenum ;i++)tmp = tmp->next;

if(tmp->arr[arrindex] != NULL){

std::cout << *tmp->arr[arrindex]; //вывести на экран содержимое

}else{

std::cerr << "\nпо указанному номеру нет данных\n";

}

…

,либо NULL если номер превышает общее количество ячеек в списке.

< void AddRecord(node* inserted = NULL) > - добавляет запись с клавиатуры в список в указанный узел определяемый указателем < node* inserted >. По умолчанию создаётся новый элемент в хвосте списка функцией < node* AddNode(int count = 1) >, в который добавляется создаваемая запись:

…

node* tmp = NULL; // временный указатель

if(inserted == NULL){

tmp = AddNode();

}else{

tmp = inserted;

}

…

Если функции был тередан узел в котором нет свободных мест, то происходит микробалансировка, происходит рекурсивный вызов самой себя но в качестве параметра передаётся функция < node* Born2newNodes(node* full) >:

…

if(tmp->instd == NODEARRLEN){ // если в узле нет свободных мест

AddRecord(Born2newNodes(tmp)); // рекурсивный вызов самой себя после

// микробалансировки и добавления 2-х новых узлов

}else{

…

Ей передаётся указатель на полностью заполненный узел < tmp >. Она «встраивает» в список два новых узла, переонсит половину записей из переданоого ей узла в первый новый и возвращает указатель на второй новый -пустой (более подробно в описании самой функции). В результате происходит разряжение маленькой области списка (микробалансировка) и запись добавляется в пустой узел.

В случае же если в переданном узле есть свободное место происходит поиск этого места, запрос на ввод данных с клавиатуры и вставка данных:

…

else{

for(int i=0; i<NODEARRLEN ; ++i){ // ищем в узле свободное место под вставку нового элемента <T>

if(tmp->arr[i] == NULL){// если нашли

tmp->arr[i] = new T; // выделяем память под новый элемент

std::cout << "\nВвод: ";

std::cin >> *tmp->arr[i]; // вводим с клавиатуры

tmp->instd++; // увеличиваем счётчик заполненных мест в узле на 1

break;

}

}//end for

}//end else

…

< node* GetHead() > - возвращает указатель на голову списка:

node* GetHead(){

return head;

}

< void Show() > - выводит на экран в пронумерованном виде все записи находящиеся в элементах списка:

…

do{

std::cout << "\n------ " << nodenum << " ------\n";

for(int i = 0; i<NODEARRLEN; ++i){

if(tmp->arr[i] != NULL)std::cout << "\n[" << i << "]: "<< *tmp->arr[i];

else std::cout << "\n[" << i << "]: ";

}

++nodenum;

tmp = tmp->next; // переходим к следующему

}while(tmp != head);

…

< void AddLogNumRecord(int num) > - добавляет в список запись с клавиатуры, согласно заданному логическому номеру< int num >, в случае если ячейка по указанному логическому номеру занята происходит её замена без предупреждения об этом пользователя и корректное освобождение памяти от старой строки:

…

if(tmp->arr[arrindex] != NULL) delete tmp->arr[arrindex]; // если место занято - освободить

tmp->arr[arrindex] = new T;

std::cout << "\nВвод: ";

std::cin >> *tmp->arr[arrindex];

tmp->instd++;

…

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

…

if(nodenum > lsize){

std::cerr << "\nвключение невозможно, сначала нужно увеличить размер списка\n";

return;

}

…

< int Leng() > - возвращает размер в байтах типа заданного шаблоном класса ( return sizeof(T)).

< void Sorting() > - осуществляет сортировку списка по длине строк. Короткие строки помещаются в начало, длинные в конец. Алгоритм сортировки основан на классическом алгоритме «сортировка выбором», модифицирован для конкретной задачи (просмотр элементов и ячеек массива в элементах).

< void Balancing() > - производит так называемую балансировку списка, разбивает каждый полностью заполненный узел на два заполненных только наполовину. Работа функции: вычисляется размер нового списка в узлах:

//******* 2 вычисляем количество необходимых узлов для нового листа ***********

const int half = NODEARRLEN/2;

int nd = 0; // количество необходимых узлов для переноса

if(fullcellcounter < half){

nd = 1;

}else{//-----------------

if(fullcellcounter <= NODEARRLEN && fullcellcounter > half){

nd = 2;

}else{//-------------------

if(fullcellcounter%half){

nd = fullcellcounter/half + 1;

}else{//-------------------

nd = fullcellcounter/half;

}

}

…

Создаём новый список:

…

node *newhead = NULL;

node *newtail = NULL;

CreateTmpList(newhead,newtail,nd);

…

Переносим записи из старого списка, в новый с разрежением:

…

newtmp->arr[m] = new T;

*newtmp->arr[m] = *tmp->arr[j];//перенос

newtmp->instd++;

delete tmp->arr[j];//освобождение памяти в старом листе

…

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

…

CyDoublewayList::~CyDoublewayList();

head = newhead;

tail = newtail;

lsize = nd;

…

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

< void SaveInTxtfile(const char* pathfilename) > - сохраняет все строки в списке в указанный файл в текстовом виде. Создаётся новый файл:

…

std::ofstream ofile(pathfilename);

…

Проверяется существование этого файла, и если его нет, то фукция завершает свою работу выводя сообщение об ошибке:

…

if(!ofile){

std::cerr << "\nОшибка создания файла!\n";

return;

}

…



Затем обход списка и вывод в файл по строкам:

…

for(int i=0; i<lsize ;i++){ // обход списка

tmp = tmp->next;

for(int j=0; j<NODEARRLEN ;j++){// обход очередного узла

if(tmp->arr[j] == NULL)continue; //пустые пропускаем

ofile << *tmp->arr[j]; //запись в файл

}

}

…

Такой вывод возможен благодаря перегруженному оператору < ofstream& operator<<> описанному далее.

< void LoadOfTxtfile(const char* pathfilename) > - создаёт необходимое количество элементов списка в хвостесписка и читает в них указанный текстовый файл:

…

while(!infile.eof()){ //пока не достигнут конец файл

tmp = AddNode(); //

for(int j=0;j<NODEARRLEN;j++){

if(infile.peek() == EOF) break; //если чтение обрвается не на конце массива не создавать новых T

tmp->arr[j] = new T;

infile >> *tmp->arr[j];

tmp->instd++;

}

…



< void AddOrderNumRecord() > - включение с сохранением порядка. Предварительно производит сортировку списка с разрешения пользователя и балансировку, и вставляет строку в позицию соответствующую её длине (напомним что критерий сортировки - длина строки):

…

for(int i = 0; i<lsize; i++){

tmp = tmp->next;

for(int j=0;j<NODEARRLEN;j++){

if(tmp->arr[j] == NULL)continue;

if(*tmp->arr[j] > *record){

for(int t = 0, z=0; t<=((half-1)-j) ; t++,z++){//цикл преноса

tmp->arr[half+z] = tmp->arr[j+t];

tmp->arr[j+t] = NULL;

}

tmp->arr[j] = record;

return;

}

}

}

…

Закрытые методы,

< void CreateTmpList(node*& phead, node*& ptail, int sz) > - создаёт временный список c указанным числом элементов < int sz >. Два указателя передаются по ссылкам, в них будут записаны адреса головы и хвоста нового списка. Метод используется при балансировке списка.

< void SwapCell(T* raz, T* dva) > - метод используется в алгоритме сортировки для обмена адресов двух указателей на объекты типа задаваемого шаблоном:

…

T *tmp = new T;

*tmp = *raz;

*raz = *dva;

*dva = *tmp;

…

< node* Born2newNodes(node* full) > - разбивает заполненный узел переданный в параметре < node* full > на два полузаполненных (так называемая микробалансировка), и возвращает указатель на второй созданный (пустой, так как половина записей остаётся в старом, половина записывается в первый созданный, а второй созданный остаётся пустым и готов к заполнению):

…

node* cpynd = AddNode(2);

int cnt_full = NODEARRLEN/2;

int cnt_copy = 0;

while(cnt_full < NODEARRLEN){

cpynd->arr[cnt_copy] = full->arr[cnt_full]; //копируем адреса в новый узел из заполненного

full->arr[cnt_full] = NULL; // освобождаем место в заполненном

cpynd->instd++; // количество в новом - растёт

full->instd--; // количество в заполненном - уменьшается

++cnt_full; // следующие две пары

++cnt_copy;

}

return cpynd->next;

…



Рис. 6. Принцип работы функции Born2newNodes()

7.2 Class StartMenu

- Является классом который обеспечивает взаимодействие программы с пользователем, выводит на экран меню и приглашения для ввода данных, хранит указатель на объект списка.

Включает в себя:

Переменную < CyDoublewayList<StringMy> * p > - указатель на обьект конкретизированного списка.

Конструктор,

< StartMenu(void) > - конструктор по умолчанию

Деструктор,

< virtual ~StartMenu(void) > - виртуальный деструктор обеспечивающий корректное освобождение памяти

Методы,

< void StartProgramm() > - выводит на экран меню, приглашения на ввод данных, вывод обработанных данных



7.3 Class StringMy

- Является контейнерным классом объекты которого хранят в себе текстовые строки и содеожат методы для работы с ними

Включает в себя:

Переменную < char *stroka > - указатель на начало строки данных

Конструктор,

< StringMy(void) > - конструктор по умолчанию

Деструктор,

< ~StringMy(void)> - деструктор обеспечивающий корректное освобождение памяти

Конструктор-копировщик,

< StringMy(const StringMy& rhs)>- обеспечивает «глубокое» копирование.

Методы,

< int leng()> - возвращает длину строки

Перегруженные операторы,

< StringMy& operator=(StringMy& rhs) > - оператор присваивания освобождает память от данных объекта которому присваивают новые данные и производит «глубокое» копирование данных:

…

this->~StringMy();

stroka = new char[DLINA];

for(int i=0; i<DLINA; ++i){

stroka[i] = rhs.stroka[i];

}

return *this;

…



< bool operator>(StringMy& rhs) > - логический оператор больше, перегруженый таким образом что возвращает true если длина первой строки больше длины второй строки:

…

if( this->leng() > rhs.leng() )return true;

return false;

…

< bool operator<(StringMy& rhs) > - логический оператор меньше, перегруженый таким образом, что возвращает true если длина первой строки меньше длины второй строки:

…

if( this->leng() < rhs.leng() )return true;

return false;

…

< bool operator==(StringMy& rhs) > - логический оператор сравнения, перегруженый таким образом, что возвращает true если длина первой строки равна длине второй строки:

…

if( this->leng() == rhs.leng() )return true;

return false;

…

Дружественные функции,

< friend std::istream& operator>>(std::istream& in_flow, StringMy& rhs) > - обеспечивает ввод строки с клавиатуры:

…

std::cin.getline(rhs.stroka,DLINA-1,'\n');

…

< friend std::ostream& operator<<(std::ostream& out_flow, StringMy& rhs) > - вывод на экран:

…

std::cout << rhs.stroka;

…

< friend std::ifstream& operator>>(std::ifstream& infiles, StringMy& rhs) > - ввод из файла:

…

std::getline(infile,buf); // читаем из файла в буфер строку

…

while(buf[i]){

rhs.stroka[i] = buf[i]; // из буфера в нашу новую строку

i++;

}

…

< friend std::ofstream& operator<<(std::ofstream& outfile, StringMy& rhs)> - вывод в файл.

…

outfile << rhs.stroka << '\n';

…



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

Программа работает в диалоговом режиме в единственном окне консоли. При запуске программы выводится меню следующего содержания (рис 7.) предоставляющее доступ ко всем функциям программы.

Рис 7. Меню программы

Для выбора пункта меню необходимо ввести соответствующую цифру и нажать Enter.



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

1) Чтобы продемонстрировать работу программы загрузим в неё список из текстового файла out.txt находящегося в одной папке с исполняемым файлом программы (Рис 8), и выведем на экран содержимое списка (Рис 9).

Рис 8. Содержимое файла out.txt

Рис 9. Данные в списке введённые из файла.

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

2) Теперь проверим работу пункта меню 2, добавив запись (our added new test string). Выведем результаты на экран (Рис 10)

Рис 10. Результат добавления записи.

Как мы видим наша строка добавлена в конец списка, но и список «разредился». Произошло это потому, что конструкция < p->AddRecord(p->GetHead()) > находящаяся в пункте меню 2, добавляет новые записи в «голову» списка, а поскольку, как видно из Рис 5 в головном узле списка все ячейки массива заняты - произошла микробалансировка, котрую осуществила функция < node* Born2newNodes(node* full) >.

3) Проверим теперь работу пункта меню 3, добавим запись по логическому номеру. По логическому номеру 10 находится строка (user#), добавим по нему строку (admin#) и выведем результат на экран (Рис 11).



Рис 11. Добавление по логическому номеру

Как мы видим программа заменила строку на новую.

4) Теперь проверим извлечение по логическому номеру - пункт меню 4. Извлечём по 6-му логическому номеру (Рис 12).

Рис 12. Извлечение по логическому номеру.

Как видим программа вернула верный результат судя по (Рис 11).

Извлекая по логическому номеру с пустой ячейкой получим следующий результат (Рис 13)



Рис 13. Сообщение об ошибке.

Действительно - в восьмой ячеке данных нет, судя по Рис 11.

5) Проверка пункта 5 включает в себя и проверку пункта 6, так как функции из пункта меню 6 включены в 5-й пункт, включение с сохранением порядка подразумевает предварительную сортировку списка. Как было сказано выше в описании функций критерий сортировки - длина строки и соответственно для включения с сохранением порядка критерий будет тот же. Добавим через 5-й пункт строку (string for 5 point) и выведем на экран список (Рис 14).