|
|
Бьерн Страуструп. Язык программирования С Второе дополненное издание
ГЛАВА 8. ШАБЛОНЫ ТИПА
Вот ваша цитата
- Бьерн Страуструп
В этой главе вводится понятие шаблона типа. С его помощью можно достаточно просто определить и реализовать без потерь в эффективности выполнения программы и, не отказываясь от статического контроля типов, такие контейнерные классы, как списки и ассоциативные массивы. Кроме того, шаблоны типа позволяют определить сразу для целого семейства типов обобщенные (генерические) функции, например, такие, как sort (сортировка). В качестве примера шаблона типов и его связи с другими конструкциями языка приводится семейство списочных классов. Чтобы показать способы получения программы из в значительной степени независимых частей, приводится несколько вариантов шаблонной функции sort(). В конце определяется простой шаблон типа для ассоциативного массива и показывается на двух небольших демонстрационных программах, как им пользоваться.
8.1 Введение
Одним из самых полезных видов классов является контейнерный класс, т.е. такой класс, который хранит объекты каких-то других типов. Списки, массивы, ассоциативные массивы и множества - все это контейнерные классы. С помощью описанных в главах 5 и 7 средств можно определить класс, как контейнер объектов единственного, известного типа. Например, в $$5.3.2 определяется множество целых. Но контейнерные классы обладают тем интересным свойством, что тип содержащихся в них объектов не имеет особого значения для создателя контейнера, но для пользователя конкретного контейнера этот тип является существенным. Следовательно, тип содержащихся объектов должен параметром контейнерного класса, и создатель такого класса будет определять его с помощью типа- параметра. Для каждого конкретного контейнера (т.е. объекта контейнерного класса) пользователь будет указывать каким должен быть тип содержащихся в нем объектов. Примером такого контейнерного класса был шаблон типа Vector из $$1.4.3.
В этой главе исследуется простой шаблон типа stack (стек) и в результате вводится понятие шаблонного класса. Затем рассматриваются более полные и правдоподобные примеры нескольких родственных шаблонов типа для списка. Вводятся шаблонные функции и формулируются правила, что может быть параметром таких функций. В конце приводится шаблон типа для ассоциативного массива.
8.2 Простой шаблон типа
Шаблон типа для класса задает способ построения отдельных классов, подобно тому, как описание класса задает способ построения его отдельных объектов. Можно определить стек, содержащий элементы произвольного типа: template 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 указывает, что описывается шаблон типа с параметром
T, обозначающим тип, и что это обозначение будет использоваться в последующем описании. После того, как идентификатор T указан в префиксе, его можно использовать как любое другое имя типа.
Область видимости T продолжается до конца описания, начавшегося префиксом template.
Бьерн Страуструп.
Язык программирования С++
205
Отметим, что в префиксе T объявляется типом, и оно не обязано быть именем класса. Так, ниже в описании объекта sc тип T оказывается просто char.
Имя шаблонного класса, за которым следует тип, заключенный в угловые скобки <>, является именем класса (определяемым шаблоном типа), и его можно использовать как все имена класса. Например, ниже определяется объект sc класса stack: stack sc(100); // стек символов
Если не считать особую форму записи имени, класс stack полностью эквивалентен классу определенному так: 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. С другой стороны, для понимания шаблона типа полезно представить себе его действие на конкретном типе, например int или shape*, прежде, чем пытаться представить его во всей общности.
Имея определение шаблонного класса stack, можно следующим образом определять и использовать различные стеки: stack ssp(200);
// стек указателей на фигуры stack sp(400);
// стек структур Point void f(stack& sc)
// параметр типа `ссылка на
// complex'
{ sc.push(complex(1,2)); complex z = 2.5*sc.pop(); stack*p = 0;
// указатель на стек целых p = new stack(800);
// стек целых размещается
// в свободной памяти for ( int i = 0; i<400; i++) { p->push(i); sp.push(Point(i,i+400));
}
//
}
Поскольку все функции-члены класса stack являются подстановками, и в этом примере транслятор создает вызовы функций только для размещения в свободной памяти и освобождения.
Функции в шаблоне типа могут и не быть подстановками, шаблонный класс stack с полным правом можно определить и так: template class stack {
T* v;
T* p;
Бьерн Страуструп. Язык программирования С++ 206 int sz; public: stack(int); stack(); void push(T); T pop(); int size() const; }; В этом случае определение функции-члена stack должно быть дано где-то в другом месте, как это и было для функций- членов обычных, нешаблонных классов. Подобные функции так же параметризируются типом, служащим параметром для их шаблонного класса, поэтому определяются они с помощью шаблона типа для функции. Если это происходит вне шаблонного класса, это надо делать явно: template void stack::push(T a)
{
*p++ = a;
} template stack::stack(int s)
{ v = p = new T[sz=s];
}
Отметим, что в пределах области видимости имени stack уточнение является избыточным, и stack::stack - имя конструктора.
Задача системы программирования, а вовсе не программиста, предоставлять версии шаблонных функций для каждого фактического параметра шаблона типа. Поэтому для приводившегося выше примера система программирования должна создать определения конструкторов для классов stack, stack и stack, деструкторов для stack и stack
, версии функций push() для stack, stack и stack и версию функции pop() для stack. Такие создаваемые функции будут совершенно обычными функциями-членами, например: void stack::push(complex a) { *p++ = a; }
Здесь отличие от обычной функции-члена только в форме имени класса. Точно так же, как в программе может быть только одно определение функции-члена класса, возможно только одно определение шаблона типа для функции-члена шаблонного класса. Если требуется определение функции-члена шаблонного класса для конкретного типа, то задача системы программирования найти шаблон типа для этой функции-члена и создать нужную версию функции. В общем случае система программирования может рассчитывать на указания от программиста, которые помогут найти нужный шаблон типа.
Важно составлять определение шаблона типа таким образом, чтобы его зависимость от глобальных данных была минимальной. Дело в том, шаблон типа будет использоваться для порождения функций и классов на основе заранее неизвестного типа и в неизвестных контекстах. Практически любая, даже слабая зависимость от контекста может проявиться как проблема при отладке программы пользователем, который, вероятнее всего, не был создателем шаблона типа. К совету избегать, насколько это возможно, использований глобальных имен, следует относиться особенно серьезно при разработке шаблона типа.
8.3 Шаблоны типа для списка
На практике при разработке класса, служащего коллекцией объектов, часто приходится учитывать взаимоотношения использующихся в реализации классов, управление памятью и необходимость определить итератор по содержимому коллекции. Часто бывает так, что несколько родственных классов разрабатываются совместно ($$12.2). В качестве примера мы предложим семейство классов, представляющих односвязные списки и шаблоны типа для них.
Бьерн Страуструп. Язык программирования С++ 207 8.3.1 Список с принудительной связью Вначале определим простой список, в котором предполагается, что в каждом заносимом в список объекте есть поле связи. Потом этот список будет использоваться как строительный материал для создания более общих списков, в которых объект не обязан иметь поле связи. Сперва в описаниях классов будет приведена только общая часть, а реализация будет дана в следующем разделе. Это делается за тем, чтобы вопросы проектирования классов не затемнялись деталями их реализации. Начнем с типа slink, определяющего поле связи в односвязном списке: struct slink { slink* next; slink() { next = 0; } slink(slink* p) { next = p; } }; Теперь можно определить класс, который может содержать объекты любого, производного от slink, класса: class slist_base { // public: int insert(slink*); // добавить в начало списка int append(slink*); // добавить к концу списка slink* get(); // удалить и возвратить начало списка // }; Такой класс можно назвать списком с принудительной связью, поскольку его можно использовать только в том случае, когда все элементы имеют поле slink, которое используется как указатель на slist_base. Само имя slist_base (базовый односвязный список) говорит, что этот класс будет использоваться как базовый для односвязных списочных классов. Как обычно, при разработке семейства родственных классов возникает вопрос, как выбирать имена для различных членов семейства. Поскольку имена классов не могут перегружаться, как это делается для имен функций, для обуздания размножения имен перегрузка нам не поможет. Класс slist_base можно использовать так: void f() { slist_base slb; slb.insert(new slink); // slink* p = slb.get(); // delete p; } Но поскольку структура slink не может содержать никакой информации помимо связи, этот пример не слишком интересен. Чтобы воспользоваться slist_base, надо определить полезный, производный от slink, класс. Например, в трансляторе используются узлы дерева программы name (имя), которые приходится связывать в список: class name : public slink { // }; void f(const char* s) { slist_base slb; slb.insert(new name(s)); // name* p = (name*)slb.get();
Бьерн Страуструп.
Язык программирования С++
208
// delete p;
}
Здесь все нормально, но поскольку определение класса slist_base дано через структуру slink, приходится использовать явное приведение типа для преобразования значения типа slink*, возвращаемого функцией slist_base::get(), в name*. Это некрасиво. Для большой программы, в которой много списков и производных от slink классов, это к тому же чревато ошибками. Нам пригодилась бы надежная по типу версия класса slist_base: template class Islist : private slist_base { public: void insert(T* a) { slist_base::insert(a); }
T* get() { return (T*) slist_base::get(); }
//
};
Приведение в функции Islist::get() совершенно оправдано и надежно, поскольку в классе Islist гарантируется, что каждый объект в списке действительно имеет тип T или тип производного от T класса. Отметим, что slist_base является частным базовым классом Islist. Мы нет хотим, чтобы пользователь случайно натолкнулся на ненадежные детали реализации.
Имя Islist (intrusive singly linked list) обозначает односвязный список с принудительной связью. Этот шаблон типа можно использовать так: void f(const char* s)
{
Islist ilst; ilst.insert(new name(s));
// name* p = ilst.get();
// delete p
}
Попытки некорректного использования будет выявлены на стадии трансляции: class expr : public slink {
//
}; void g(expr* e)
{
Islist ilst; ilst.insert(e);
// ошибка: Islist::insert(),
// а нужно name*
//
}
Нужно отметить несколько важных моментов относительно нашего примера. Во-первых, решение надежно в смысле типов (преграда тривиальным ошибкам ставится в очень ограниченной части программы, а именно, в функциях доступа из Islist). Во-вторых, надежность типов достигается без увеличения затрат времени и памяти, поскольку функции доступа из Islist тривиальны и реализуются подстановкой. В-третьих, поскольку вся настоящая работа со списком делается в реализации класса slist_base (пока еще не представленной), никакого дублирования функций не происходит, а исходный текст реализации, т.е. функции slist_base, вообще не должен быть доступен пользователю. Это может быть существенно в коммерческом использовании служебных программ для списков. Кроме того, достигается разделение между интерфейсом и его реализацией, и становится возможной смена реализации без перетрансляции программ пользователя. Наконец, простой список с принудительной связью близок по использованию памяти и времени к оптимальному решению. Иными словами, такой подход близок к оптимальному по времени, памяти, упрятыванию данных и контролю типов и в тоже
Бьерн Страуструп. Язык программирования С++ 209 время он обеспечивает большую гибкость и компактность выражений. К сожалению, объект может попасть в Islist только, если он является производным от slink. Значит нельзя иметь список Islist из значений типа int, нельзя составить список из значений какого-то ранее определенного типа, не являющегося производным от slink. Кроме того, придется постараться, чтобы включить объект в два списка Islist ($$6.5.1). 8.3.2 Список без принудительной связи После "экскурса" в вопросы построения и использования списка с принудительной связью перейдем к построению списков без принудительной связи. Это значит, что элементы списка не обязаны содержать дополнительную информацию, помогающую в реализации списочного класса. Поскольку мы больше не можем рассчитывать, что объект в списке имеет поле связи, такую связь надо предусмотреть в реализации: template struct Tlink : public slink {
T info;
Tlink(const T& a) : info(a) { }
};
Класс Tlink хранит копию объектов типа T помимо поля связи, которое идет от его базового класса slink. Отметим, что используется инициализатор в виде info(a), а не присваивание info=a. Это существенно для эффективности операции в случае типов, имеющих нетривиальные конструкторы копирования и операции присваивания ($$7.11). Для таких типов (например, для String) определив конструктор как
Tlink(const T& a) { info = a; } мы получим, что будет строиться стандартный объект String, а уже затем ему будет присваиваться значение. Имея класс, определяющий связь, и класс Islist, получить определение списка без принудительной связи совсем просто: template class Slist : private slist_base { public: void insert(const T& a)
{ slist_base::insert(new
Tlink(a));
} void append(const T& a)
{ slist_base::append(new
Tlink(a));
}
T get();
//
}; template
T Slist::get()
{
Tlink* lnk = (Tlink*) slist_base::get();
T i = lnk->info; delete lnk; return i;
}
Работать со списком Slist так же просто, как и со списком Ilist. Различие в том, что можно включать в
Slist объект, класс которого не является производным от slink, а также можно включать один объект в два списка: void f(int i)
{
Slist lst1;
Slist lst2; lst1.insert(i);
Бьерн Страуструп. Язык программирования С++ 210 lst2.insert(i); // int i1 = lst1.get(); int i2 = lst2.get(); // } Однако, список с принудительной связью, например Islist, позволял создавать существенно более эффективную программу и давал более компактное представление. Действительно, при каждом включении объекта в список Slist нужно разместить объект Tlink, а при каждом удалении объекта из Slist нужно удалить объект Tlink, причем каждый раз копируется объект типа T. Когда возникает такая проблема дополнительных расходов, могут помочь два приема. Во-первых, Tlink является прямым кандидатом для размещения с помощью практически оптимальной функции размещения специального назначения (см. $$5.5.6). Тогда дополнительные расходы при выполнении программы сократятся до обычно приемлемого уровня. Во-вторых, полезным оказывается такой прием, когда объекты хранятся в "первичном" списке, имеющим принудительную связь, а списки без принудительной связи используются только, когда требуется включение объекта в несколько списков: void f(name* p) { Islist lst1;
Slist lst2; lst1.insert(p);
// связь через объект `*p' lst2.insert(p);
//
для хранения `p' используется
// отдельный объект типа список
//
}
Конечно, подобные трюки можно делать только в отдельном компоненте программы, чтобы не допустить путаницы списочных типов в интерфейсах различных компонент. Но это именно тот случай, когда ради эффективности и компактности программы на них стоит идти.
Поскольку конструктор Slist копирует параметр для insert(), список Slist пригоден только для таких небольших объектов, как целые, комплексные числа или указатели. Если для объектов копирование слишком накладно или неприемлемо по смысловым причинам, обычно выход бывает в том, чтобы вместо объектов помещать в список указатели на них. Это сделано в приведенной выше функции f() для lst2.
Отметим, что раз параметр для Slist::insert() копируется, передача объекта производного класса функции insert(), ожидающей объект базового класса, не пройдет гладко, как можно было (по наивности) подумать: class smiley : public circle {
/* ... */ }; void g1(Slist& olist, const smiley& grin)
{ olist.insert(grin);
// ловушка!
}
В список будет включена только часть circle объекта типа smiley. Отметим, что эта неприятность будет обнаружена транслятором в том случае, который можно считать наиболее вероятным. Так, если бы рассматриваемый базовый класс был абстрактным, транслятор запретил бы "урезание" объекта производного класса: void g2(Slist& olist, const circle& c)
{ olist.insert(c);
// ошибка: попытка создать объект
// абстрактного класса
}
Чтобы избежать "урезания" объекта нужно использовать указатели: void g3(Slist& plist, const smiley& grin)
{
Бьерн Страуструп. Язык программирования С++ 211 olist.insert(&grin); // прекрасно } Не нужно использовать параметр-ссылку для шаблонного класса: void g4(Slist & rlist, const smiley& grin)
{ rlist.insert(grin);
// ошибка: будет созданы команды,
// содержащие ссылку на ссылку (shape&&)
}
При генерации по шаблону типа ссылки, используемые подобным образом, приведут ошибкам в типах.
Генерация по шаблону типа для функции
Slist::insert(T&); приведет к появлению недопустимой функции
Slist::insert(shape&&);
Ссылка не является объектом, поэтому нельзя иметь ссылку на ссылку.
Поскольку список указателей является полезной конструкцией, имеет смысл дать ему специальное имя: template class Splist : private Slist { public: void insert(T* p) { Slist::insert(p); } void append(T* p) { Slist::append(p); }
T* get() { return (T*) Slist::get(); }
}; class Isplist : private slist_base { public: void insert(T* p) { slist_base::insert(p); } void append(T* p) { slist_base::append(p); }
T* get() { return (T*) slist_base::get(); }
};
Эти определения к тому же улучшают контроль типов и еще больше сокращают необходимость дублировать функции.
Часто бывает полезно, чтобы тип элемента, указываемый в шаблоне типа, сам был шаблонным классом. Например, разреженную матрицу, содержащую даты, можно определить так: typedef Slist< Slist > dates;
Обратите внимание на наличие пробелов в этом определении. Если между первой и второй угловой скобкой > нет пробелов, возникнет синтаксическая ошибка, поскольку >> в определении typedef Slist> dates; будет трактоваться как операция сдвига вправо. Как обычно, вводимое в typedef имя служит синонимом обозначаемого им типа, а не является новым типом. Конструкция typedef полезна для именования для длинных имен шаблонных классов также, как она полезна для любых других длинных имен типов.
Отметим, что параметр шаблона типа, который может по разному использоваться в его определении, должен все равно указываться среди списка параметров шаблона один раз. Поэтому шаблон типа, в котором используется объект T и список элементов T, надо определять так: template class mytemplate {
T ob;
Slist slst;
//
}; а вовсе не так:
Бьерн Страуструп. Язык программирования С++ 212 template > class mytemplate {
T obj;
Slist slst;
//
};
В $$8.6 и $$R.14.2 даны правила, что может быть параметром шаблона типа.
|
|
|
Скачать 2.87 Mb.