Чтение онлайн

Рассмотрим такое написание класса 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 что-нибудь из пустого списка. Мы обсудим это в #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 (* // для индикации конца итерации возвращает 0 // для всех типов не идеален, хорош для указателей ent ret = ce ? (ce=ce-»next)-»e : 0; if (ce == cs-»last) ce= 0; return ret; *) *);

Фактически класс 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“; *)