C++
Шрифт:
7.3.1 Интерфейс
Рассмотрим такое написание класса 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;*) *);
В
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'ов, а видно только в закрытой части и определниях функций.
7.3.2 Реализация
Реализующие slist функции в основном просты. Единственая настоящая сложность – что делать в случае ошибки, если, например, пользователь попытается get что-нибудь из пустого списка. Мы обсудим это в #7.3.4. Здесь приводятся определения членов 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 (его описание можно найти в #7.3.4). Этот указатель на имя функции используется точно так же, как если бы он был именем функции. Это является краткой формой более явной записи вызова:
(*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 как друга, поэтому мы можем описать подходящий итератор. Вот один, написанный в духе #6.8:
class slist_iterator (* slink* ce; slist* cs; public: slist_iterator(slist amp; s) (* cs = amp;s; ce = cs-»last; *)
ent operator (* //
7.3.3 Как этим пользоваться
Фактически класс slist в написанном виде бесполезен. В конечном счете, зачем можно использовать список указателей void*? Штука в том, чтобы вывести класс из slist и получить список тех объектов, которые представляют интерес в конкреной программе. Представим компилятор языка вроде С++. В нем широко будут использоваться списки имен; имя name – это нечто вроде
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*, которые используются в качестве фактических параметров (#2.3.4).
Списки имен можно использовать в классе, который предтавляет определение класса:
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( amp;friends,n)) error(«friend redeclared»); // friend переописан else if (find( amp;members,n)) error(«friend redeclared as member»); // friend переописан как member else friends.append(n); *) if (n-»is_operator) operators.append(n); // ... *)
где is_operator и 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'ов, приведено в #7.3.5. Печатать 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“; *)