После того, как описаны средства языка, которые относятся к производным классам, обсуждение снова может вернуться к стоящим задачам. В классах, которые описываются в этом разделе, основополагающая идея состоит в том, что они однажды написаны, а потом их используют программисты, которые не могут изменить их определение. Физически классы состоят из одного или более заголовочных файлов, определяющих интерфейс, и одного или более файлов, определяющих реализацию. Заголовочные файлы будут помещены куда-то туда, откуда пользователь может взять их копии с помощью директивы #include. Файлы, определяющие реализацию, обычно компилируют и помещают в библиотеку.
Интерфейс
Рассмотрим такое написание класса slist для однократно связанного списка, с помощью которого можно создавать как однородные, так и неоднородные списки объектов тех типов, которые еще должны быть определены. Сначала мы определим тип ent:
typedef void* ent;
Точная сущность типа ent несущественна, но нужно, чтобы в нем мог храниться указатель. Тогдамыопределимтип slink:
class slink {
friend class slist;
friend class slist_iterator;
slink* next;
ent e;
slink(ent a, slink* p) { e=a; next=p;}
};
В одном звене может храниться один ent, и с помощью него реализуется класс slist:
class slist {
friend class slist_iterator;
slink* last; // last->next - головасписка
public:
int insert(ent a); // добавить в голову списка
int append(ent a); // добавить в хвост списка
ent get(); // вернуться и убрать голову списка
void clear(); // убрать все звенья
slist() { last=0; }
slist(ent a) { last=new slink(a,0); last->next=last; }
~slist() { clear(); }
};
Хотя список очевидным образом реализуется как связанный список, реализацию можно изменить так, чтобы использовался вектор из ent"ов, не повлияв при этом на пользователей. То есть, применение slink"ов никак не видно в описаниях открытых функций slist"ов, а видно только в закрытой части и определениях функций.
Реализация
Реализующие slist функции в основном просты. Единственная настоящая сложность - что делать в случае ошибки, если, например, пользователь попытается get() что-нибудь из пустого списка. Здесь приводятся определения членов slist. Обратите внимание, как хранение указателя на последний элемент кругового списка дает возможность просто реализовать оба действия append() и insert():
int slist::insert(ent a)
{
if (last)
last->next = new slink(a,last->next);
else {
last = new slink(a,0);
last->next = last;
}
return 0;
}
int slist::append(ent a)
{
if (last)
last = last->next = new slink(a,last->next);
else {
last = new slink(a,0);
last->next = last;
}
return 0;
}
ent slist::get()
{
if (last == 0) slist_handler("get fromempty list");
// взять из пустого списка
slink* f = last->next;
ent r f->e;
if (f == last)
last = 0;
else
last->next = f->next;
delete f;
return f;
}
Обратите внимание, как вызывается slist_handler. Этот указатель на имя функции используется точно так же, как если бы он был именем функции. Это является краткой формой более явной записи вызова:
(*slist_handler)("get fromempty list");
И slist::clear(), наконец, удаляет из списка все элементы:
void slist::clear()
{
slink* l = last;
if (l == 0) return;
do {
slink* ll = l;
l = l->next;
delete ll;
} while (l!=last);
}
Класс slist не обеспечивает способа заглянуть в список, но только средства для вставления и удаления элементов. Однако оба класса, и slist, и slink, описывают класс slist_iterator как друга, поэтому мы можем описать подходящий итератор. Вот один, написанный в духе этого пункта:
class slist_iterator {
slink* ce;
slist* cs;
public:
slist_iterator(slist& s) { cs = &s; ce = cs->last; }
ent operator()() {
// для индикации конца итерации возвращает 0
// для всех типов не идеален, хорош для указателей
ent ret = ce ? (ce=ce->next)->e : 0;
if (ce == cs->last) ce= 0;
return ret;
}
};
Как Этим Пользоваться
Фактически класс slist в написанном виде бесполезен. В конечном счете, зачем можно использовать список указателей void*? Штука в том, чтобы вывести класс из slist и получить список тех объектов, которые представляют интерес в конкретной программе. Представим компилятор языка вроде C++. В нем широко будут использоваться списки имен; имя - это нечто вроде
struct name {
char* string;
// ...
};
В список будут помещаться указатели на имена, а не сами объекты имена. Это позволяет использовать небольшое информационное поле e slist"а, и дает возможность имени находиться одновременно более чем в одном списке. Вот определение класса nlist, который очень просто выводится из класса slist:
#include "slist.h"
#include "name.h"
struct nlist : slist {
void insert(name* a) { slist::insert(a); }
void append(name* a) { slist::append(a); }
name* get() {}
nlist(name* a) : (a) {}
};
Функции нового класса или наследуются от slist непосредственно, или ничего не делают кроме преобразования типа. Класс nlist - это ничто иное, как альтернативный интерфейс класса slist. Так как на самом деле тип ent есть void*, нет необходимости явно преобразовывать указатели name*, которые используются в качестве фактических параметров .
Списки имен можно использовать в классе, который представляет определение класса:
struct classdef {
nlist friends;
nlist constructors;
nlist destructors;
nlist members;
nlist operators;
nlist virtuals;
// ...
void add_name(name*);
classdef();
~classdef();
};
и имена могут добавляться к этим спискам приблизительно так:
void classdef::add_name(name* n)
{
if (n->is_friend()) {
if (find(&friends,n))
error("friend redeclared");
else if (find(&members,n))
error("friend redeclared as member");
else
friends.append(n);
}
if (n->is_operator()) operators.append(n);
// ...
}
где is_iterator() и is_friend() являются функциями членами класса name. Фукнцию find() можнонаписатьтак:
int find(nlist* ll, name* n)
{
slist_iterator ff(*(slist*)ll);
ent p;
while ( p=ff() ) if (p==n) return 1;
return 0;
}
Здесь применяется явное преобразование типа, чтобы применить slist_iterator к nlist. Более хорошее решение, - сделать итератор для nlist"ов. Печатать nlist может, например, такая функция:
void print_list(nlist* ll, char* list_name)
{
slist_iterator count(*(slist*)ll);
name* p;
int n = 0;
while ( count() ) n++;
cout << list_name << "\n" << n << "members\n";
slist_iterator print(*(slist*)ll);
while ( p=(name*)print() ) cout << p->string << "\n";
}
Обработка Ошибок
Есть четыре подхода к проблеме, что же делать, когда во время выполнения общецелевое средство вроде slist сталкивается с ошибкой (в C++ нет никаких специальных средств языка для обработке ошибок):
Возвращать недопустимое значение и позволить пользователю его проверять;
Возвращать дополнительное значение состояния и разрешить пользователю проверять его;
Вызывать функцию ошибок, заданную как часть класса slist; или
Вызывать функцию ошибок, которую предположительно предоставляет пользователь.
Для небольшой программы, написанной ее единственным пользователем, нет фактически никаких особенных причин предпочесть одно из этих решений другим. Для средства общего назначения ситуация совершенно иная.
Первый подход, возвращать недопустимое значение, неосуществим. Нет совершенно никакого способа узнать, что некоторое конкретное значение будет недопустимым во всех применениях slist.
Второй подход, возвращать значение состояния, можно использовать в некоторых классах (один из вариантов этого плана применяется в стандартных потоках ввода/вывода istream и ostream). Здесь, однако, имеется серьезная проблема, вдруг пользователь не позаботится проверить значение состояния, если средство не слишком часто подводит. Кроме того, средство может использоваться в сотнях или даже тысячах мест программы. Проверка значения в каждом месте сильно затруднит чтение программы.
Третьему подходу, предоставлять функцию ошибок, недостает гибкости. Тот, кто реализует общецелевое средство, не может узнать, как пользователи захотят, чтобы обрабатывались ошибки. Например, пользователь может предпочитать сообщения на датском или венгерском.
Четвертый подход, позволить пользователю задавать функцию ошибок, имеет некоторую привлекательность при условии, что разработчик предоставляет класс в виде библиотеки (#4.5), в которой содержатся стандартные функции обработки ошибок. Решения 3 и 4 можно сделать более гибкими (и по сути эквивалентными), задав указатель на функцию, а не саму функцию. Это позволит разработчику такого средства, как slist, предоставить функцию ошибок, действующую по умолчанию, и при этом программистам, которые будут использовать списки, будет легко задать свои собственные функции ошибок, если нужно, и там, где нужно.
Например:
typedef void (*PFC)(char*); // указатель на тип функция
extern PFC slist_handler;
extern PFC set_slist_handler(PFC);
Функция set_slist_hanlder() позволяет пользователю заменить стандартную функцию. Общепринятая реализация предоставляет действующую по умолчанию функцию обработки ошибок, которая сначала пишет сообщение об ошибке в cerr, после чего завершает программу с помощью exit():
#include "slist.h"
#include
void default_error(char* s)
{
cerr << s << "\n";
exit(1);
}
Она описывает также указатель на функцию ошибок и, для удобства записи, функцию для ее установки:
PFC slist_handler = default_error;
PFC set_slist_handler(PFC handler);
{
PFC rr = slist_handler;
slist_handler = handler;
return rr;
}
Обратитевнимание, как set_slist_hanlder() возвращаетпредыдущий slist_hanlder(). Это делает удобным установку и переустановку обработчиков ошибок на манер стека. Это может быть в основном полезным в больших программах, в которых slist может использоваться в нескольких разных ситуациях, в каждой из которых могут, таким образом, задаваться свои собственные подпрограммы обработки ошибок.
Например:
{
PFC old = set_slist_handler(my_handler);
// код, в котором в случае ошибок в slist
// будет использоваться мой обработчик my_handler
set_slist_handler(old); // восстановление
}
Чтобы сделать управление более изящным, slist_hanlder мог бы быть сделан членом класса slist, что позволило бы различным спискам иметь одновременно разные обработчики.
Обобщенные Классы
Очевидно, можно было бы определить списки других типов (classdef*, int, char* и т.д.) точно так же, как был определен класс nlist: простым выводом из класса slist. Процесс определения таких новых типов утомителен (и потому чреват ошибками), но с помощью макросов его можно "механизировать". К сожалению, если пользоваться стандартным C препроцессором, это тоже может оказаться тягостным. Однако полученными в результате макросами пользоваться довольно просто.
Вот пример того, как обобщенный (generic) класс slist, названный gslist, может быть задан как макрос. Сначала для написания такого рода макросов включаются некоторые инструменты из :
.html#include "slist.h"
#ifndef GENERICH
#include
#endif
Обратите внимание на использование #ifndef для того, чтобы гарантировать, что в одной компиляции не будет включен дважды. GENERICH определен в .
После этого с помощью name2(), макроса из для конкатенации имен, определяются имена новых обобщенных классов:
#define gslist(type) name2(type,gslist)
#define gslist_iterator(type) name2(type,gslist_iterator)
И, наконец, можно написать классы gslist(тип) и gslist_iterator(тип):
#define gslistdeclare(type) \
struct gslist(type) : slist { \
int insert(type a) \
{ return slist::insert( ent(a) ); } \
int append(type a) \
{ return slist::append( ent(a) ); } \
type get() { return type( slist::get() ); } \
gslist(type)() { } \
gslist(type)(type a) : (ent(a)) { } \
~gslist(type)() { clear(); } \
}; \
\
struct gslist_iterator(type) : slist_iterator { \
gslist_iterator(type)(gslist(type)& a) \
: ( (slist&)s ) {} \
type operator()() \
{ return type( slist_iterator::operator()() ); } \
}
\ на конце строк указывает , что следующая строка является частью определяемого макроса.
С помощью этого макроса список указателей на имя, аналогичный использованному раньше классу nlist, можно определить так:
#include "name.h"
typedef name* Pname;
declare(gslist,Pname); // описатькласс gslist(Pname)
gslist(Pname) nl; // описатьодин gslist(Pname)
Макрос declare (описать) определен в . Он конкатенирует свои параметры и вызывает макрос с этим именем, в данном случае gslistdeclare, описанный выше. Параметр имя типа для declare должен быть простым именем. Используемый метод макроопределения не может обрабатывать имена типов вроде name*, поэтому применяется typedef.
Использования вывода класса гарантирует, что все частные случаи обобщенного класса разделяют код. Этот метод можно применять только для создания классов объектов того же размера или меньше, чем базовый класс, который используется в макросе.
Ограниченные Интерфейсы
Класс slist - довольно общего характера. Иногда подобная общность не требуется или даже нежелательна. Ограниченные виды списков, такие как стеки и очереди, даже более обычны, чем сам обобщенный список. Такие структуры данных можно задать, не описав базовый класс как открытый. Например, очередь целых можно определить так:
#include "slist.h"
class iqueue : slist {
//предполагается sizeof(int)<=sizeof(void*)
public:
void put(int a) { slist::append((void*)a); }
int det() { return int(slist::get()); }
iqueue() {}
};
При таком выводе осуществляются два логически разделенных действия: понятие списка ограничивается понятием очереди (сводится к нему), и задается тип int, чтобы свести понятие очереди к типу данных очередь целых, iqueue. Эти два действия можно выполнять и раздельно. Здесь первая часть - это список, ограниченный так, что он может использоваться только как стек:
#include "slist.h"
class stack : slist {
public:
slist::insert;
slist::get;
stack() {}
stack(ent a) : (a) {}
};
который потом используется для создания типа "стек указателей на символы":
#include "stack.h"
class cp : stack {
public:
void push(char* a) { slist::insert(a); }
char* pop() { return (char*)slist::get(); }
nlist() {}
};
|
