Страница:
классов 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; }
Здесь отличие от обычной функции-члена только в форме имени класса.
Точно так же, как в программе может быть только одно определение
функции-члена класса, возможно только одно определение шаблона
типа для функции-члена шаблонного класса. Если требуется определение
функции-члена шаблонного класса для конкретного типа, то задача системы
программирования найти шаблон типа для этой функции-члена и создать
нужную версию функции. В общем случае система программирования
может рассчитывать на указания от программиста, которые помогут
найти нужный шаблон типа.
Важно составлять определение шаблона типа таким образом, чтобы
его зависимость от глобальных данных была минимальной. Дело в том,
шаблон типа будет использоваться для порождения функций и классов
на основе заранее неизвестного типа и в неизвестных контекстах.
Практически любая, даже слабая зависимость от контекста может
проявиться как проблема при отладке программы пользователем, который,
вероятнее всего, не был создателем шаблона типа. К совету избегать,
насколько это возможно, использований глобальных имен, следует
относиться особенно серьезно при разработке шаблона типа.
На практике при разработке класса, служащего коллекцией объектов,
часто приходится учитывать взаимоотношения использующихся в реализации
классов, управление памятью и необходимость определить итератор по
содержимому коллекции. Часто бывает так, что несколько родственных
классов разрабатываются совместно ($$12.2). В качестве примера мы
предложим семейство классов, представляющих односвязные списки и
шаблоны типа для них.
Вначале определим простой список, в котором предполагается, что
в каждом заносимом в список объекте есть поле связи. Потом этот
список будет использоваться как строительный материал для создания
более общих списков, в которых объект не обязан иметь поле связи.
Сперва в описаниях классов будет приведена только общая часть,
а реализация будет дана в следующем разделе. Это делается за тем,
чтобы вопросы проектирования классов не затемнялись деталями их
реализации.
Начнем с типа 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();
// ...
delete p;
}
Здесь все нормально, но поскольку определение класса slist_base
дано через структуру slink, приходится использовать явное приведение
типа для преобразования значения типа slink*, возвращаемого
функцией slist_base::get(), в name*. Это некрасиво. Для большой
программы, в которой много списков и производных от slink классов,
это к тому же чревато ошибками. Нам пригодилась бы надежная по
типу версия класса slist_base:
template<class T>
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<name> ilst;
ilst.insert(new name(s));
// ...
name* p = ilst.get();
// ...
delete p
}
Попытки некорректного использования будет выявлены на стадии
трансляции:
class expr : public slink {
// ...
};
void g(expr* e)
{
Islist<name> ilst;
ilst.insert(e); // ошибка: Islist<name>::insert(),
// а нужно name*
// ...
}
Нужно отметить несколько важных моментов относительно нашего примера.
Во-первых, решение надежно в смысле типов (преграда тривиальным
ошибкам ставится в очень ограниченной части программы, а именно,
в функциях доступа из Islist). Во-вторых, надежность типов
достигается без увеличения затрат времени и памяти, поскольку
функции доступа из Islist тривиальны и реализуются подстановкой.
В-третьих, поскольку вся настоящая работа со списком делается в
реализации класса slist_base (пока еще не представленной), никакого
дублирования функций не происходит, а исходный текст реализации,
т.е. функции slist_base, вообще не должен быть доступен пользователю.
Это может быть существенно в коммерческом использовании служебных
программ для списков. Кроме того, достигается разделение между
интерфейсом и его реализацией, и становится возможной смена реализации
без перетрансляции программ пользователя. Наконец, простой список
с принудительной связью близок по использованию памяти и времени
к оптимальному решению. Иными словами, такой подход близок к
оптимальному по времени, памяти, упрятыванию данных и контролю
типов и в тоже время он обеспечивает большую гибкость и компактность
выражений.
К сожалению, объект может попасть в Islist только, если он
является производным от slink. Значит нельзя иметь список Islist
из значений типа int, нельзя составить список из значений какого-то
ранее определенного типа, не являющегося производным от slink.
Кроме того, придется постараться, чтобы включить объект в два списка
Islist ($$6.5.1).
После "экскурса" в вопросы построения и использования списка с
принудительной связью перейдем к построению списков без принудительной
связи. Это значит, что элементы списка не обязаны содержать
дополнительную информацию, помогающую в реализации списочного класса.
Поскольку мы больше не можем рассчитывать, что объект в списке
имеет поле связи, такую связь надо предусмотреть в реализации:
template<class T>
struct Tlink : public slink {
T info;
Tlink(const T& a) : info(a) { }
};
Класс Tlink<T> хранит копию объектов типа T помимо поля связи, которое
идет от его базового класса slink. Отметим, что используется
инициализатор в виде info(a), а не присваивание info=a. Это
существенно для эффективности операции в случае типов, имеющих
нетривиальные конструкторы копирования и операции присваивания
($$7.11). Для таких типов (например, для String) определив конструктор
как
Tlink(const T& a) { info = a; }
мы получим, что будет строиться стандартный объект String, а уже
затем ему будет присваиваться значение.
Имея класс, определяющий связь, и класс Islist, получить
определение списка без принудительной связи совсем просто:
template<class T>
class Slist : private slist_base {
public:
void insert(const T& a)
{ slist_base::insert(new Tlink<T>(a)); }
void append(const T& a)
{ slist_base::append(new Tlink<T>(a)); }
T get();
// ...
};
template<class T>
T Slist<T>::get()
{
Tlink<T>* lnk = (Tlink<T>*) slist_base::get();
T i = lnk->info;
delete lnk;
return i;
}
Работать со списком Slist так же просто, как и со списком Ilist.
Различие в том, что можно включать в Slist объект, класс которого не
является производным от slink, а также можно включать один объект
в два списка:
void f(int i)
{
Slist<int> lst1;
Slist<int> lst2;
lst1.insert(i);
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<name> lst1;
Slist<name*> lst2;
lst1.insert(p); // связь через объект `*p'
lst2.insert(p); // для хранения `p' используется
// отдельный объект типа список
// ...
}
Конечно, подобные трюки можно делать только в отдельном компоненте
программы, чтобы не допустить путаницы списочных типов в
интерфейсах различных компонент. Но это именно тот случай, когда
ради эффективности и компактности программы на них стоит идти.
Поскольку конструктор Slist копирует параметр для insert(),
список Slist пригоден только для таких небольших объектов, как
целые, комплексные числа или указатели. Если для объектов копирование
слишком накладно или неприемлемо по смысловым причинам, обычно
выход бывает в том, чтобы вместо объектов помещать в список
указатели на них. Это сделано в приведенной выше функции f() для
lst2.
Отметим, что раз параметр для Slist::insert() копируется, передача
объекта производного класса функции insert(), ожидающей объект
базового класса, не пройдет гладко, как можно было (по наивности)
подумать:
class smiley : public circle { /* ... */ };
void g1(Slist<circle>& olist, const smiley& grin)
{
olist.insert(grin); // ловушка!
}
В список будет включена только часть circle объекта типа smiley.
Отметим, что эта неприятность будет обнаружена транслятором в том
случае, который можно считать наиболее вероятным. Так, если бы
рассматриваемый базовый класс был абстрактным, транслятор запретил
бы "урезание" объекта производного класса:
void g2(Slist<shape>& olist, const circle& c)
{
olist.insert(c); // ошибка: попытка создать объект
// абстрактного класса
}
Чтобы избежать "урезания" объекта нужно использовать указатели:
void g3(Slist<shape*>& plist, const smiley& grin)
{
olist.insert(&grin); // прекрасно
}
Не нужно использовать параметр-ссылку для шаблонного класса:
void g4(Slist<shape&>& rlist, const smiley& grin)
{
rlist.insert(grin); // ошибка: будет созданы команды,
// содержащие ссылку на ссылку (shape&&)
}
При генерации по шаблону типа ссылки, используемые подобным образом,
приведут ошибкам в типах. Генерация по шаблону типа для функции
Slist::insert(T&);
приведет к появлению недопустимой функции
Slist::insert(shape&&);
Ссылка не является объектом, поэтому нельзя иметь ссылку на ссылку.
Поскольку список указателей является полезной конструкцией,
имеет смысл дать ему специальное имя:
template<class T>
class Splist : private Slist<void*> {
public:
void insert(T* p) { Slist<void*>::insert(p); }
void append(T* p) { Slist<void*>::append(p); }
T* get() { return (T*) Slist<void*>::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<date> > dates;
Обратите внимание на наличие пробелов в этом определении. Если между
первой и второй угловой скобкой > нет пробелов, возникнет
синтаксическая ошибка, поскольку >> в определении
typedef Slist<Slist<date>> dates;
будет трактоваться как операция сдвига вправо. Как обычно, вводимое
в typedef имя служит синонимом обозначаемого им типа, а не является
новым типом. Конструкция typedef полезна для именования для
длинных имен шаблонных классов также, как она полезна для любых
других длинных имен типов.
Отметим, что параметр шаблона типа, который может по разному
использоваться в его определении, должен все равно указываться среди
списка параметров шаблона один раз. Поэтому шаблон типа, в котором
используется объект T и список элементов T, надо определять так:
template<class T> class mytemplate {
T ob;
Slist<T> slst;
// ...
};
а вовсе не так:
template<class T, class Slist<t> > class mytemplate {
T obj;
Slist<T> slst;
// ...
};
В $$8.6 и $$R.14.2 даны правила, что может быть параметром шаблона
типа.
Реализация функций slist_base очевидна. Единственная трудность
связана с обработкой ошибок. Например, что делать если пользователь
с помощью функции get() пытается взять элемент из пустого списка.
Подобные ситуации разбираются в функции обработки ошибок
slist_handler(). Более развитый метод, рассчитанный на особые
ситуации, будет обсуждаться в главе 9.
Приведем полное описание класса slist_base:
class slist_base {
slink* last; // last->next является началом списка
public:
void insert(slink* a); // добавить в начало списка
void append(slink* a); // добавить в конец списка
slink* get(); // удалить и возвратить
// начало списка
void clear() { last = 0; }
slist_base() { last = 0; }
slist_base(slink* a) { last = a->next = a; }
friend class slist_base_iter;
};
Чтобы упростить реализацию обеих функций insert и append, хранится
указатель на последний элемент замкнутого списка:
void slist_base_insert(slink* a) // добавить в начало списка
{
if (last)
a->next = last->next;
else
last = a;
last->next = a;
}
Заметьте, что last->next - первый элемент списка.
void slist_base::append(slink* a) // добавить в конец списка
{
if (last) {
a->next = last->next;
last = last->next = a;
}
else
last = a->next = a;
}
slist* slist_base::get() // удалить и возвратить начало списка
{
if (last == 0)
slist_handler("нельзя взять из пустого списка");
slink* f = last->next;
if (f== last)
last = 0;
else
last->next = f->next;
return f;
}
Возможно более гибкое решение, когда slist_handler - указатель на
функцию, а не сама функция. Тогда вызов
slist_handler("нельзя взять из пустого списка");
будет задаваться так
(*slist_handler)(" нельзя взять из пустого списка");
Как мы уже делали для функции new_handler ($$3.2.6), полезно
завести функцию, которая поможет пользователю создавать свои
обработчики ошибок:
typedef void (*PFV)(const char*);
PFV set_slist_handler(PFV a)
{
PFV old = slist_handler;
slist_handler = a;
return old;
}
PFV slist_handler = &default_slist_handler;
Особые ситуации, которые обсуждаются в главе 9, не только дают
альтернативный способ обработки ошибок, но и способ реализации
slist_handler.
В классе slist_base нет функций для просмотра списка, можно только
вставлять и удалять элементы. Однако, в нем описывается как друг
класс slist_base_iter, поэтому можно определить подходящий для
списка итератор. Вот один из возможных, заданный в том стиле, какой
был показан в $$7.8:
class slist_base_iter {
slink* ce; // текущий элемент
slist_base* cs; // текущий список
public:
inline slist_base_iter(slist_base& s);
inline slink* operator()()
};
slist_base_iter::slist_base_iter(slist_base& s)
{
cs = &s;
ce = cs->last;
}
slink* slist_base_iter::operator()()
// возвращает 0, когда итерация кончается
{
slink* ret = ce ? (ce=ce->next) : 0;
if (ce == cs->last) ce = 0;
return ret;
}
Исходя из этих определений, легко получить итераторы для Slist и
Islist. Сначала надо определить дружественные классы для итераторов
по соответствующим контейнерным классам:
template<class T> class Islist_iter;
template<class T> class Islist {
friend class Islist_iter<T>;
// ...
};
template<class T> class Slist_iter;
template<class T> class Slist {
friend class Slist_iter<T>;
// ...
};
Обратите внимание, что имена итераторов появляются без определения
их шаблонного класса. Это способ определения в условиях взаимной
зависимости шаблонов типа.
Теперь можно определить сами итераторы:
template<class T>
class Islist_iter : private slist_base_iter {
public:
Islist_iter(Islist<T>& s) : slist_base_iter(s) { }
T* operator()()
{ return (T*) slist_base_iter::operator()(); }
};
template<class T>
class Slist_iter : private slist_base_iter {
public:
Slist_iter(Slist<T>& s) : slist_base_iter(s) { }
inline T* operator()();
};
T* Slist_iter::operator()()
{
return ((Tlink<T>*) slist_base_iter::operator()())->info;
}
Заметьте, что мы опять использовали прием, когда из одного базового
класса строится семейство производных классов (а именно, шаблонный
класс). Мы используем наследование, чтобы выразить общность классов
и избежать ненужного дублирования функций. Трудно переоценить
стремление избежать дублирования функций при реализации таких простых
и часто используемых классов как списки и итераторы. Пользоваться
этими итераторами можно так:
void f(name* p)
{
Islist<name> lst1;
Slist<name> lst2;
lst1.insert(p);
lst2.insert(p);
// ...
Islist_iter<name> iter1(lst1);
const name* p;
while (p=iter1()) {
list_iter<name> iter2(lst1);
const name* q;
while (q=iter2()) {
if (p == q) cout << "найден" << *p << '\n';
}
}
}
Есть несколько способов задать итератор для контейнерного класса.
Разработчик программы или библиотеки должен выбрать один из них
и придерживаться его. Приведенный способ может показаться слишком
хитрым. В более простом варианте можно было просто переименовать
operator()() как next(). В обоих вариантах предполагается взаимосвязь
между контейнерным классом и итератором для него, так что можно
при выполнении итератора обработать случаи, когда элементы добавляются
или удаляются из контейнера. Этот и некоторые другие способы задания
итераторов были бы невозможны, если бы итератор зависел от функции
пользователя, в которой есть указатели на элементы из контейнера.
Как правило, контейнер или его итераторы реализуют понятие "установить
итерацию на начало" и понятие "текущего элемента".
Если понятие текущего элемента предоставляет не итератор, а сам
контейнер, итерация происходит в принудительном порядке по отношению
к контейнеру аналогично тому, как поля связи принудительно хранятся
в объектах из контейнера. Значит трудно одновременно вести две
итерации для одного контейнера, но расходы на память и время при такой
организации итерации близки к оптимальным. Приведем пример:
class slist_base {
// ...
slink* last; // last->next голова списка
slink* current; // текущий элемент
public:
// ...
slink* head() { return last?last->next:0; }
slink* current() { return current; }
void set_current(slink* p) { current = p; }
slink* first() { set_current(head()); return current; }
slink* next();
slink* prev();
};
Подобно тому, как в целях эффективности и компактности программы
можно использовать для одного объекта как список с принудительной
связью, так и список без нее, для одного контейнера можно
использовать принудительную и непринудительную итерацию:
void f(Islist<name>& ilst)
// медленный поиск имен-дубликатов
{
list_iter<name> slow(ilst); // используется итератор
name* p;
while (p = slow()) {
ilst.set_current(p); // рассчитываем на текущий элемент
name* q;
while (q = ilst.next())
if (strcmp(p->string,q->string) == 0)
cout << "дубликат" << p << '\n';
}
}
Еще один вид итераторов показан в $$8.8.
Использование шаблонных классов означает наличие шаблонных
функций-членов. Помимо этого, можно определить глобальные шаблонные
функции, т.е. шаблоны типа для функций, не являющихся членами класса.
Шаблон типа для функций порождает семейство функций точно также,
как шаблон типа для класса порождает семейство классов. Эту возможность
мы обсудим на последовательности примеров, в которых приводятся
варианты функции сортировки sort(). Каждый из вариантов в последующих
разделах будет иллюстрировать общий метод.
Как обычно мы сосредоточимся на организации программы, а не на
разработке ее алгоритма, поэтому использоваться будет тривиальный
алгоритм. Все варианты шаблона типа для sort() нужны для того,
чтобы показать возможности языка м полезные приемы программирования.
Варианты не упорядочены в соответствии с тем, насколько они хороши.
Кроме того, можно обсудить и традиционные варианты без шаблонов типа,
в частности, передачу указателя на функцию, производящую сравнение.
Начнем с простейшего шаблона для sort():
template<class T> void sort(Vector<T>&);
void f(Vector<int>& vi,
Vector<String>& vc,
Vector<int>& vi2,
Vector<char*>& vs)
{
sort(vi); // sort(Vector<int>& v);
sort(vc); // sort(Vector<String>& v);
sort(vi2); // sort(Vector<int>& v);
sort(vs); // sort(Vector<char*>& v);
}
Какая именно функция sort() будет вызываться определяется фактическим
параметром. Программист дает определение шаблона типа для функции,
а задача системы программирования обеспечить создание правильных
вариантов функции по шаблону и вызов соответствующего варианта.
Например, простой шаблон с алгоритмом пузырьковой сортировки можно
определить так:
template<class T> void sort(Vector<T>& v)
/*
Сортировка элементов в порядке возрастания
Используется сортировка по методу пузырька
*/
{
unsigned n = v.size();
for (int i=0; i<n-1; i++)
for (int j=n-1; i<j; j--)
if (v[j] < v[j-1]) { // меняем местами v[j] и v[j-1]
T temp = v[j];
v[j] = v[j-1];
v[j-1] = temp;
}
}
Советуем сравнить это определение с функцией сортировки с тем же
алгоритмом из $$4.6.9. Существенное отличие этого варианта в том,
что вся необходимая информация передается в единственном параметре
v. Поскольку тип сортируемых элементов известен (из типа фактического
параметра, можно непосредственно сравнивать элементы, а не передавать
указатель на производящую сравнение функцию. Кроме того, нет нужды
возиться с операцией sizeof. Такое решение кажется более красивым
и к тому же оно более эффективно, чем обычное. Все же оно сталкивается
с трудностью. Для некоторых типов операция < не определена, а для
других, например char*, ее определение противоречит тому, что
требуется в приведенном определении шаблонной функции. (Действительно,
нам нужно сравнивать не указатели на строки, а сами строки).
В первом случае попытка создать вариант sort() для таких типов
закончится неудачей (на что и следует надеяться) , а во втором
появиться функция, производящая неожиданный результат.
Чтобы правильно сортировать вектор из элементов char* мы можем
просто задать самостоятельно подходящее определение функции
sort(Vector<char*>&):
void sort(Vector<char*>& v)
{
unsigned n = v.size();
for (int i=0; i<n-1; i++)
for ( int j=n-1; i<j; j--)
if (strcmp(v[j],v[j-1])<0) {
// меняем местами v[j] и v[j-1]
char* temp = v[j];
v[j] = v[j-1];
v[j-1] = temp;
}
}
Поскольку для векторов из указателей на строки пользователь дал
свое особое определение функции sort(), оно и будет использоваться,
а создавать для нее определение по шаблону с параметром типа
Vector<char*>& не нужно. Возможность дать для особо важных или
"необычных" типов свое определение шаблонной функции дает ценное
качество гибкости в программировании и может быть важным средством
доведения программы до оптимальных характеристик.
В предыдущем разделе функция сравнения была "встроенной" в теле
sort() (просто использовалась операция <). Возможно другое решение,
когда ее предоставляет сам шаблонный класс Vector. Однако, такое
решение имеет смысл только при условии, что для типов элементов
возможно осмысленное понятие сравнения. Обычно в такой ситуации
функцию sort() определяют только для векторов, на которых определена
операция < :
template<class T> void sort(SortableVector<T>& v)
{
unsigned n = v.size();
for (int i=0; i<n-1; i++)
for (int j=n-1; i<j; j--)
if (v.lessthan(v[j],v[j-1])) {
// меняем местами v[j] и v[j-1]
T temp = v[j];
v[j] = v[j-1];
v[j-1] = temp;
}
}
Класс SortableVector (сортируемый вектор) можно определить так:
template<class T> class SortableVector
: public Vector<T>, public Comparator<T> {
public:
SortableVector(int s) : Vector<T>(s) { }
stack<shape*> и stack<Point>, версии функций push() для stack<complex>,
stack<int> и stack<Point> и версию функции pop() для stack<complex>.
Такие создаваемые функции будут совершенно обычными функциями-членами,
например:
void stack<complex>::push(complex a) { *p++ = a; }
Здесь отличие от обычной функции-члена только в форме имени класса.
Точно так же, как в программе может быть только одно определение
функции-члена класса, возможно только одно определение шаблона
типа для функции-члена шаблонного класса. Если требуется определение
функции-члена шаблонного класса для конкретного типа, то задача системы
программирования найти шаблон типа для этой функции-члена и создать
нужную версию функции. В общем случае система программирования
может рассчитывать на указания от программиста, которые помогут
найти нужный шаблон типа.
Важно составлять определение шаблона типа таким образом, чтобы
его зависимость от глобальных данных была минимальной. Дело в том,
шаблон типа будет использоваться для порождения функций и классов
на основе заранее неизвестного типа и в неизвестных контекстах.
Практически любая, даже слабая зависимость от контекста может
проявиться как проблема при отладке программы пользователем, который,
вероятнее всего, не был создателем шаблона типа. К совету избегать,
насколько это возможно, использований глобальных имен, следует
относиться особенно серьезно при разработке шаблона типа.
На практике при разработке класса, служащего коллекцией объектов,
часто приходится учитывать взаимоотношения использующихся в реализации
классов, управление памятью и необходимость определить итератор по
содержимому коллекции. Часто бывает так, что несколько родственных
классов разрабатываются совместно ($$12.2). В качестве примера мы
предложим семейство классов, представляющих односвязные списки и
шаблоны типа для них.
Вначале определим простой список, в котором предполагается, что
в каждом заносимом в список объекте есть поле связи. Потом этот
список будет использоваться как строительный материал для создания
более общих списков, в которых объект не обязан иметь поле связи.
Сперва в описаниях классов будет приведена только общая часть,
а реализация будет дана в следующем разделе. Это делается за тем,
чтобы вопросы проектирования классов не затемнялись деталями их
реализации.
Начнем с типа 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();
// ...
delete p;
}
Здесь все нормально, но поскольку определение класса slist_base
дано через структуру slink, приходится использовать явное приведение
типа для преобразования значения типа slink*, возвращаемого
функцией slist_base::get(), в name*. Это некрасиво. Для большой
программы, в которой много списков и производных от slink классов,
это к тому же чревато ошибками. Нам пригодилась бы надежная по
типу версия класса slist_base:
template<class T>
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<name> ilst;
ilst.insert(new name(s));
// ...
name* p = ilst.get();
// ...
delete p
}
Попытки некорректного использования будет выявлены на стадии
трансляции:
class expr : public slink {
// ...
};
void g(expr* e)
{
Islist<name> ilst;
ilst.insert(e); // ошибка: Islist<name>::insert(),
// а нужно name*
// ...
}
Нужно отметить несколько важных моментов относительно нашего примера.
Во-первых, решение надежно в смысле типов (преграда тривиальным
ошибкам ставится в очень ограниченной части программы, а именно,
в функциях доступа из Islist). Во-вторых, надежность типов
достигается без увеличения затрат времени и памяти, поскольку
функции доступа из Islist тривиальны и реализуются подстановкой.
В-третьих, поскольку вся настоящая работа со списком делается в
реализации класса slist_base (пока еще не представленной), никакого
дублирования функций не происходит, а исходный текст реализации,
т.е. функции slist_base, вообще не должен быть доступен пользователю.
Это может быть существенно в коммерческом использовании служебных
программ для списков. Кроме того, достигается разделение между
интерфейсом и его реализацией, и становится возможной смена реализации
без перетрансляции программ пользователя. Наконец, простой список
с принудительной связью близок по использованию памяти и времени
к оптимальному решению. Иными словами, такой подход близок к
оптимальному по времени, памяти, упрятыванию данных и контролю
типов и в тоже время он обеспечивает большую гибкость и компактность
выражений.
К сожалению, объект может попасть в Islist только, если он
является производным от slink. Значит нельзя иметь список Islist
из значений типа int, нельзя составить список из значений какого-то
ранее определенного типа, не являющегося производным от slink.
Кроме того, придется постараться, чтобы включить объект в два списка
Islist ($$6.5.1).
После "экскурса" в вопросы построения и использования списка с
принудительной связью перейдем к построению списков без принудительной
связи. Это значит, что элементы списка не обязаны содержать
дополнительную информацию, помогающую в реализации списочного класса.
Поскольку мы больше не можем рассчитывать, что объект в списке
имеет поле связи, такую связь надо предусмотреть в реализации:
template<class T>
struct Tlink : public slink {
T info;
Tlink(const T& a) : info(a) { }
};
Класс Tlink<T> хранит копию объектов типа T помимо поля связи, которое
идет от его базового класса slink. Отметим, что используется
инициализатор в виде info(a), а не присваивание info=a. Это
существенно для эффективности операции в случае типов, имеющих
нетривиальные конструкторы копирования и операции присваивания
($$7.11). Для таких типов (например, для String) определив конструктор
как
Tlink(const T& a) { info = a; }
мы получим, что будет строиться стандартный объект String, а уже
затем ему будет присваиваться значение.
Имея класс, определяющий связь, и класс Islist, получить
определение списка без принудительной связи совсем просто:
template<class T>
class Slist : private slist_base {
public:
void insert(const T& a)
{ slist_base::insert(new Tlink<T>(a)); }
void append(const T& a)
{ slist_base::append(new Tlink<T>(a)); }
T get();
// ...
};
template<class T>
T Slist<T>::get()
{
Tlink<T>* lnk = (Tlink<T>*) slist_base::get();
T i = lnk->info;
delete lnk;
return i;
}
Работать со списком Slist так же просто, как и со списком Ilist.
Различие в том, что можно включать в Slist объект, класс которого не
является производным от slink, а также можно включать один объект
в два списка:
void f(int i)
{
Slist<int> lst1;
Slist<int> lst2;
lst1.insert(i);
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<name> lst1;
Slist<name*> lst2;
lst1.insert(p); // связь через объект `*p'
lst2.insert(p); // для хранения `p' используется
// отдельный объект типа список
// ...
}
Конечно, подобные трюки можно делать только в отдельном компоненте
программы, чтобы не допустить путаницы списочных типов в
интерфейсах различных компонент. Но это именно тот случай, когда
ради эффективности и компактности программы на них стоит идти.
Поскольку конструктор Slist копирует параметр для insert(),
список Slist пригоден только для таких небольших объектов, как
целые, комплексные числа или указатели. Если для объектов копирование
слишком накладно или неприемлемо по смысловым причинам, обычно
выход бывает в том, чтобы вместо объектов помещать в список
указатели на них. Это сделано в приведенной выше функции f() для
lst2.
Отметим, что раз параметр для Slist::insert() копируется, передача
объекта производного класса функции insert(), ожидающей объект
базового класса, не пройдет гладко, как можно было (по наивности)
подумать:
class smiley : public circle { /* ... */ };
void g1(Slist<circle>& olist, const smiley& grin)
{
olist.insert(grin); // ловушка!
}
В список будет включена только часть circle объекта типа smiley.
Отметим, что эта неприятность будет обнаружена транслятором в том
случае, который можно считать наиболее вероятным. Так, если бы
рассматриваемый базовый класс был абстрактным, транслятор запретил
бы "урезание" объекта производного класса:
void g2(Slist<shape>& olist, const circle& c)
{
olist.insert(c); // ошибка: попытка создать объект
// абстрактного класса
}
Чтобы избежать "урезания" объекта нужно использовать указатели:
void g3(Slist<shape*>& plist, const smiley& grin)
{
olist.insert(&grin); // прекрасно
}
Не нужно использовать параметр-ссылку для шаблонного класса:
void g4(Slist<shape&>& rlist, const smiley& grin)
{
rlist.insert(grin); // ошибка: будет созданы команды,
// содержащие ссылку на ссылку (shape&&)
}
При генерации по шаблону типа ссылки, используемые подобным образом,
приведут ошибкам в типах. Генерация по шаблону типа для функции
Slist::insert(T&);
приведет к появлению недопустимой функции
Slist::insert(shape&&);
Ссылка не является объектом, поэтому нельзя иметь ссылку на ссылку.
Поскольку список указателей является полезной конструкцией,
имеет смысл дать ему специальное имя:
template<class T>
class Splist : private Slist<void*> {
public:
void insert(T* p) { Slist<void*>::insert(p); }
void append(T* p) { Slist<void*>::append(p); }
T* get() { return (T*) Slist<void*>::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<date> > dates;
Обратите внимание на наличие пробелов в этом определении. Если между
первой и второй угловой скобкой > нет пробелов, возникнет
синтаксическая ошибка, поскольку >> в определении
typedef Slist<Slist<date>> dates;
будет трактоваться как операция сдвига вправо. Как обычно, вводимое
в typedef имя служит синонимом обозначаемого им типа, а не является
новым типом. Конструкция typedef полезна для именования для
длинных имен шаблонных классов также, как она полезна для любых
других длинных имен типов.
Отметим, что параметр шаблона типа, который может по разному
использоваться в его определении, должен все равно указываться среди
списка параметров шаблона один раз. Поэтому шаблон типа, в котором
используется объект T и список элементов T, надо определять так:
template<class T> class mytemplate {
T ob;
Slist<T> slst;
// ...
};
а вовсе не так:
template<class T, class Slist<t> > class mytemplate {
T obj;
Slist<T> slst;
// ...
};
В $$8.6 и $$R.14.2 даны правила, что может быть параметром шаблона
типа.
Реализация функций slist_base очевидна. Единственная трудность
связана с обработкой ошибок. Например, что делать если пользователь
с помощью функции get() пытается взять элемент из пустого списка.
Подобные ситуации разбираются в функции обработки ошибок
slist_handler(). Более развитый метод, рассчитанный на особые
ситуации, будет обсуждаться в главе 9.
Приведем полное описание класса slist_base:
class slist_base {
slink* last; // last->next является началом списка
public:
void insert(slink* a); // добавить в начало списка
void append(slink* a); // добавить в конец списка
slink* get(); // удалить и возвратить
// начало списка
void clear() { last = 0; }
slist_base() { last = 0; }
slist_base(slink* a) { last = a->next = a; }
friend class slist_base_iter;
};
Чтобы упростить реализацию обеих функций insert и append, хранится
указатель на последний элемент замкнутого списка:
void slist_base_insert(slink* a) // добавить в начало списка
{
if (last)
a->next = last->next;
else
last = a;
last->next = a;
}
Заметьте, что last->next - первый элемент списка.
void slist_base::append(slink* a) // добавить в конец списка
{
if (last) {
a->next = last->next;
last = last->next = a;
}
else
last = a->next = a;
}
slist* slist_base::get() // удалить и возвратить начало списка
{
if (last == 0)
slist_handler("нельзя взять из пустого списка");
slink* f = last->next;
if (f== last)
last = 0;
else
last->next = f->next;
return f;
}
Возможно более гибкое решение, когда slist_handler - указатель на
функцию, а не сама функция. Тогда вызов
slist_handler("нельзя взять из пустого списка");
будет задаваться так
(*slist_handler)(" нельзя взять из пустого списка");
Как мы уже делали для функции new_handler ($$3.2.6), полезно
завести функцию, которая поможет пользователю создавать свои
обработчики ошибок:
typedef void (*PFV)(const char*);
PFV set_slist_handler(PFV a)
{
PFV old = slist_handler;
slist_handler = a;
return old;
}
PFV slist_handler = &default_slist_handler;
Особые ситуации, которые обсуждаются в главе 9, не только дают
альтернативный способ обработки ошибок, но и способ реализации
slist_handler.
В классе slist_base нет функций для просмотра списка, можно только
вставлять и удалять элементы. Однако, в нем описывается как друг
класс slist_base_iter, поэтому можно определить подходящий для
списка итератор. Вот один из возможных, заданный в том стиле, какой
был показан в $$7.8:
class slist_base_iter {
slink* ce; // текущий элемент
slist_base* cs; // текущий список
public:
inline slist_base_iter(slist_base& s);
inline slink* operator()()
};
slist_base_iter::slist_base_iter(slist_base& s)
{
cs = &s;
ce = cs->last;
}
slink* slist_base_iter::operator()()
// возвращает 0, когда итерация кончается
{
slink* ret = ce ? (ce=ce->next) : 0;
if (ce == cs->last) ce = 0;
return ret;
}
Исходя из этих определений, легко получить итераторы для Slist и
Islist. Сначала надо определить дружественные классы для итераторов
по соответствующим контейнерным классам:
template<class T> class Islist_iter;
template<class T> class Islist {
friend class Islist_iter<T>;
// ...
};
template<class T> class Slist_iter;
template<class T> class Slist {
friend class Slist_iter<T>;
// ...
};
Обратите внимание, что имена итераторов появляются без определения
их шаблонного класса. Это способ определения в условиях взаимной
зависимости шаблонов типа.
Теперь можно определить сами итераторы:
template<class T>
class Islist_iter : private slist_base_iter {
public:
Islist_iter(Islist<T>& s) : slist_base_iter(s) { }
T* operator()()
{ return (T*) slist_base_iter::operator()(); }
};
template<class T>
class Slist_iter : private slist_base_iter {
public:
Slist_iter(Slist<T>& s) : slist_base_iter(s) { }
inline T* operator()();
};
T* Slist_iter::operator()()
{
return ((Tlink<T>*) slist_base_iter::operator()())->info;
}
Заметьте, что мы опять использовали прием, когда из одного базового
класса строится семейство производных классов (а именно, шаблонный
класс). Мы используем наследование, чтобы выразить общность классов
и избежать ненужного дублирования функций. Трудно переоценить
стремление избежать дублирования функций при реализации таких простых
и часто используемых классов как списки и итераторы. Пользоваться
этими итераторами можно так:
void f(name* p)
{
Islist<name> lst1;
Slist<name> lst2;
lst1.insert(p);
lst2.insert(p);
// ...
Islist_iter<name> iter1(lst1);
const name* p;
while (p=iter1()) {
list_iter<name> iter2(lst1);
const name* q;
while (q=iter2()) {
if (p == q) cout << "найден" << *p << '\n';
}
}
}
Есть несколько способов задать итератор для контейнерного класса.
Разработчик программы или библиотеки должен выбрать один из них
и придерживаться его. Приведенный способ может показаться слишком
хитрым. В более простом варианте можно было просто переименовать
operator()() как next(). В обоих вариантах предполагается взаимосвязь
между контейнерным классом и итератором для него, так что можно
при выполнении итератора обработать случаи, когда элементы добавляются
или удаляются из контейнера. Этот и некоторые другие способы задания
итераторов были бы невозможны, если бы итератор зависел от функции
пользователя, в которой есть указатели на элементы из контейнера.
Как правило, контейнер или его итераторы реализуют понятие "установить
итерацию на начало" и понятие "текущего элемента".
Если понятие текущего элемента предоставляет не итератор, а сам
контейнер, итерация происходит в принудительном порядке по отношению
к контейнеру аналогично тому, как поля связи принудительно хранятся
в объектах из контейнера. Значит трудно одновременно вести две
итерации для одного контейнера, но расходы на память и время при такой
организации итерации близки к оптимальным. Приведем пример:
class slist_base {
// ...
slink* last; // last->next голова списка
slink* current; // текущий элемент
public:
// ...
slink* head() { return last?last->next:0; }
slink* current() { return current; }
void set_current(slink* p) { current = p; }
slink* first() { set_current(head()); return current; }
slink* next();
slink* prev();
};
Подобно тому, как в целях эффективности и компактности программы
можно использовать для одного объекта как список с принудительной
связью, так и список без нее, для одного контейнера можно
использовать принудительную и непринудительную итерацию:
void f(Islist<name>& ilst)
// медленный поиск имен-дубликатов
{
list_iter<name> slow(ilst); // используется итератор
name* p;
while (p = slow()) {
ilst.set_current(p); // рассчитываем на текущий элемент
name* q;
while (q = ilst.next())
if (strcmp(p->string,q->string) == 0)
cout << "дубликат" << p << '\n';
}
}
Еще один вид итераторов показан в $$8.8.
Использование шаблонных классов означает наличие шаблонных
функций-членов. Помимо этого, можно определить глобальные шаблонные
функции, т.е. шаблоны типа для функций, не являющихся членами класса.
Шаблон типа для функций порождает семейство функций точно также,
как шаблон типа для класса порождает семейство классов. Эту возможность
мы обсудим на последовательности примеров, в которых приводятся
варианты функции сортировки sort(). Каждый из вариантов в последующих
разделах будет иллюстрировать общий метод.
Как обычно мы сосредоточимся на организации программы, а не на
разработке ее алгоритма, поэтому использоваться будет тривиальный
алгоритм. Все варианты шаблона типа для sort() нужны для того,
чтобы показать возможности языка м полезные приемы программирования.
Варианты не упорядочены в соответствии с тем, насколько они хороши.
Кроме того, можно обсудить и традиционные варианты без шаблонов типа,
в частности, передачу указателя на функцию, производящую сравнение.
Начнем с простейшего шаблона для sort():
template<class T> void sort(Vector<T>&);
void f(Vector<int>& vi,
Vector<String>& vc,
Vector<int>& vi2,
Vector<char*>& vs)
{
sort(vi); // sort(Vector<int>& v);
sort(vc); // sort(Vector<String>& v);
sort(vi2); // sort(Vector<int>& v);
sort(vs); // sort(Vector<char*>& v);
}
Какая именно функция sort() будет вызываться определяется фактическим
параметром. Программист дает определение шаблона типа для функции,
а задача системы программирования обеспечить создание правильных
вариантов функции по шаблону и вызов соответствующего варианта.
Например, простой шаблон с алгоритмом пузырьковой сортировки можно
определить так:
template<class T> void sort(Vector<T>& v)
/*
Сортировка элементов в порядке возрастания
Используется сортировка по методу пузырька
*/
{
unsigned n = v.size();
for (int i=0; i<n-1; i++)
for (int j=n-1; i<j; j--)
if (v[j] < v[j-1]) { // меняем местами v[j] и v[j-1]
T temp = v[j];
v[j] = v[j-1];
v[j-1] = temp;
}
}
Советуем сравнить это определение с функцией сортировки с тем же
алгоритмом из $$4.6.9. Существенное отличие этого варианта в том,
что вся необходимая информация передается в единственном параметре
v. Поскольку тип сортируемых элементов известен (из типа фактического
параметра, можно непосредственно сравнивать элементы, а не передавать
указатель на производящую сравнение функцию. Кроме того, нет нужды
возиться с операцией sizeof. Такое решение кажется более красивым
и к тому же оно более эффективно, чем обычное. Все же оно сталкивается
с трудностью. Для некоторых типов операция < не определена, а для
других, например char*, ее определение противоречит тому, что
требуется в приведенном определении шаблонной функции. (Действительно,
нам нужно сравнивать не указатели на строки, а сами строки).
В первом случае попытка создать вариант sort() для таких типов
закончится неудачей (на что и следует надеяться) , а во втором
появиться функция, производящая неожиданный результат.
Чтобы правильно сортировать вектор из элементов char* мы можем
просто задать самостоятельно подходящее определение функции
sort(Vector<char*>&):
void sort(Vector<char*>& v)
{
unsigned n = v.size();
for (int i=0; i<n-1; i++)
for ( int j=n-1; i<j; j--)
if (strcmp(v[j],v[j-1])<0) {
// меняем местами v[j] и v[j-1]
char* temp = v[j];
v[j] = v[j-1];
v[j-1] = temp;
}
}
Поскольку для векторов из указателей на строки пользователь дал
свое особое определение функции sort(), оно и будет использоваться,
а создавать для нее определение по шаблону с параметром типа
Vector<char*>& не нужно. Возможность дать для особо важных или
"необычных" типов свое определение шаблонной функции дает ценное
качество гибкости в программировании и может быть важным средством
доведения программы до оптимальных характеристик.
В предыдущем разделе функция сравнения была "встроенной" в теле
sort() (просто использовалась операция <). Возможно другое решение,
когда ее предоставляет сам шаблонный класс Vector. Однако, такое
решение имеет смысл только при условии, что для типов элементов
возможно осмысленное понятие сравнения. Обычно в такой ситуации
функцию sort() определяют только для векторов, на которых определена
операция < :
template<class T> void sort(SortableVector<T>& v)
{
unsigned n = v.size();
for (int i=0; i<n-1; i++)
for (int j=n-1; i<j; j--)
if (v.lessthan(v[j],v[j-1])) {
// меняем местами v[j] и v[j-1]
T temp = v[j];
v[j] = v[j-1];
v[j-1] = temp;
}
}
Класс SortableVector (сортируемый вектор) можно определить так:
template<class T> class SortableVector
: public Vector<T>, public Comparator<T> {
public:
SortableVector(int s) : Vector<T>(s) { }