ГЛАВА 8. ШАБЛОНЫ ТИПА

Вот ваша цитата - Бьерн Страуструп

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

8.1 Введение

Одним из самых полезных видов классов является контейнерный класс, т.е. такой класс, который хранит объекты каких-то других типов. Списки, массивы, ассоциативные массивы и множества - все это контейнерные классы. С помощью описанных в главах 5 и 7 средств можно определить класс, как контейнер объектов единственного, известного типа. Например, в $$5.3.2 определяется множество целых. Но контейнерные классы обладают тем интересным свойством, что тип содержащихся в них объектов не имеет особого значения для создателя контейнера, но для пользователя конкретного контейнера этот тип является существенным. Следовательно, тип содержащихся объектов должен параметром контейнерного класса, и создатель такого класса будет определять его с помощью типа-параметра. Для каждого конкретного контейнера (т.е. объекта контейнерного класса) пользователь будет указывать каким должен быть тип содержащихся в нем объектов. Примером такого контейнерного класса был шаблон типа Vector из $$1.4.3.

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

8.2 Простой шаблон типа

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

template<class T> class stack {

T* v;

T* p;

int sz; public:

stack(int s) { v = p = new T[sz=s]; } ~stack() { delete[] v; } void push(T a) { *p++ = a; } T pop() { return *--p; } int size() const { return p-v; }

Для простоты не учитывался контроль динамических ошибок. Не считая этого, пример полный и вполне правдоподобный. Префикс template<class T> указывает, что описывается шаблон типа с параметром T, обозначающим тип, и что это обозначение будет использоваться в последующем описании. После того, как идентификатор T указан в префиксе, его можно использовать как любое другое имя типа. Область видимости T продолжается до конца описания, начавшегося префиксом template<class T>.

sc.push(complex(1,2)); complex z = 2.5*sc.pop();

stack<int>*p = 0; указатель на стек целых

p = new stack<int>(800); стек целых размещается

в свободной памяти

for ( int i = 0; i<400; {

p->push(i);

sp.push(Point(i,i+400));

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

Функции в шаблоне типа могут и не быть подстановками, шаблонный класс stack с полным правом можно определить и так:

template<class T> class stack { T* v; T* p;

Отметим, что в префиксе T объявляется типом, и оно не обязано быть именем класса. Так, ниже в описании объекта sc тип T оказывается просто char.

Имя шаблонного класса, за которым следует тип, заключенный в угловые скобки <>, является именем класса (определяемым шаблоном типа), и его можно использовать как все имена класса. Например, ниже определяется объект sc класса stack<char>:

stack<char> sc(100); стек символов

Если не считать особую форму записи имени, класс stack<char> полностью эквивалентен классу определенному так:

class stack char { char* v; char* p; int sz; public:

stack char(int s) { v = p = new char[sz=s]; } ~stack char() { delete[] v; } void push(char a) { *p++ = a; } char pop() { return *--p; } int size() const { return p-v; }

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

Обычно имеет смысл вначале отладить конкретный класс, такой, например, как stack char, прежде, чем строить на его основе шаблон типа stack<T>. С другой стороны, для понимания шаблона типа полезно представить себе его действие на конкретном типе, например int или shape*, прежде, чем пытаться представить его во всей общности.

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

stack<shape*> ssp(200); стек указателей на фигуры

stack<Point> sp(400); стек структур Point

void f(stack<complex>& sc) параметр типа ссылка на

complex

int sz; public:

stack(int);

~stack();

void push(T);

T pop();

int size() const;

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

template<class T> void stack<T>::push(T a)

*p++ = a;

template<class T> stack<T>::stack(int s)

v = p = new T[sz=s];

Отметим, что в пределах области видимости имени stack<T> уточнение <T> является избыточным, и stack<T>::stack - имя конструктора.

Задача системы программирования, а вовсе не программиста, предоставлять версии шаблонных функций для каждого фактического параметра шаблона типа. Поэтому для приводившегося выше примера система программирования должна создать определения конструкторов для классов stack<shape*>, stack<Point> и stack<int>, деструкторов для stack<shape*> и stack<Point>, версии функций push() для stack<complex>, stack<int> и stack<Point> и версию функции pop() для stack<complex>. Такие создаваемые функции будут совершенно обычными функциями-членами, например:

void stack<complex>::push(complex a) { *p++ = a; }

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

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

8.3 Шаблоны типа для списка

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