Мюррей Хилл - C++

table::table(int sz) (* if (sz « 0) error(„отрицательный размер таблицы“); tbl = new name*[size=sz];

for (int i = 0; i«sz; i++) tbl[i] = 0; *)

table::~table() (* for (int i = 0; i«size; i++) for (name* n = tbl[i]; n; n=n-»next) (* delete n-»string; delete n; *) delete tbl; *)

Описав деструктор для класса name можно получить более простой и ясный вариант table::~table(). Функция просмотра практически идентична той, которая использовалась в примере настольного калькулятора (#3.1.3):

#include «string.h»

name* table::look(char* p, int ins) (* int ii = 0; char* pp = p; while (*pp) ii = ii««1 ^ *pp++; if (ii « 0) ii = -ii; ii %= size;

for (name* n=tbl[ii]; n; n=n-»next) if (strcmp(p,n-»string) == 0) return n;

if (ins == 0) error(«имя не найдено»);

name* nn = new name; nn-»string = new char[strlen(p)+1]; strcpy(nn-»string,p); nn-»value = 1; nn-»next = tbl[ii]; tbl[ii] = nn; return nn;

*)

Очевидно, что функции члены класса должны заново комплироваться всегда, когда вносится какое-либо изменение в опсание класса. В идеале такое изменение никак не должно отржаться на пользователях класса. К сожалению, это не так. Для размещения переменной классового типа компилятор должен знать размер объекта класса. Если размер этих объектов меняется, то файлы, в которых класс используется, нужно компилировать зново. Можно написать такую программу (и она уже написана), которая определяет множество (минимальное) файлов, которое необходимо компилировать заново после изменения описания класса, но пока что широкого распространения она не получила.

Почему, можете вы спросить, С++ разработан так, что поле изменения закрытой части необходима новая компиляция ползователей класса? И действительно, почему вообще закрытая часть должна быть представлена в описании класса? Другими словами, раз пользователям класса не разрешается обращаться к закрытым членам, почему их описания должны приводиться в зголовочных файлах, которые, как предполагается, пользователь читает? Ответ – эффективность. Во многих системах и процесс компиляции, и последовательность операций, реализующих вызов функции, проще, когда размер автоматических объектов (объетов в стеке) известен во время компиляции.

Этой сложности можно избежать, представив каждый объект класса как указатель на «настоящий» объект. Так как все эти указатели будут иметь одинаковый размер, а размещение «настящих» объектов можно определить в файле, где доступна закртая часть, то это может решить проблему. Однако решение поразумевает дополнительные ссылки по памяти при обращении к членам класса, а также, что еще хуже, каждый вызов функции с автоматическим объектом класса включает по меньшей мере один вызов программ выделения и освобождения свободной памяти. Это сделало бы также невозможным реализацию inline-функций члнов, которые обращаются к данным закрытой части. Более того, такое изменение сделает невозможным совместную компоновку C и С++ программ (поскольку C компилятор обрабатывает struct не так, как это будет делать С++ компилятор). Для С++ это было сочтено неприемлемым.

Программирование без сокрытия данных (с применением структур) требует меньшей продуманности, чем программирование со сокрытием данных (с использованием классов). Структуру можно определить не слишком задумываясь о том, как ее предплагается использовать. А когда определяется класс, все внимние сосредотачивается на обеспечении нового типа полным мнжеством операций; это важное смещение акцента. Время, потраченное на разработку нового типа, обычно многократно окупается при разработке и тестировании программы.

Вот пример законченного типа intset, который реализует понятие «множество целых»:

class intset (* int cursize, maxsize; int *x; public: intset(int m, int n); // самое большее, m int'ов в 1..n ~intset();

int member(int t); // является ли t элементом? void insert(int t); // добавить "t" в множество

void iterate(int amp; i) (* i = 0; *) int ok(int amp; i) (* return i«cursize; *) int next(int amp; i) (* return x[i++]; *) *);

Чтобы протестировать этот класс, можно создать и распчатать множество случайных целых чисел. Такое множество могло бы быть результатом розыгрыша лотереи. Это простое множество можно также использовать для проверки последовательности цлых на повторы. Но для большинства приложений тип множество должен быть немного более проработанным. Как всегда, возможны ошибки:

#include «stream.h»

void error(char* s) (* cerr «„ "set: " «« s «« «\n“; exit(1); *)

Класс intset используется в main(), которая предполагает два целых параметра. Первый параметр задает число случайных чисел, которые нужно сгенерировать. Второй параметр указывает диапазон, в котором должны лежать случайные целые:

main(int argc, char* argv[]) (* if (argc != 3) error(«ожидается два параметра»); int count = 0; int m = atoi(argv[1]); // число элементов множества int n = atoi(argv[2]); // в диапазоне 1..n intset s(m,n);

while (count«m) (* int t = randint(n); if (s.member(t)==0) (* s.insert(t); count++; *) *)

print_in_order( amp;s); *)

В программе, для которой требуется два параметра, счечик числа параметров, argc, должен равняться трем, потому что имя программы всегда передается как argv[0]. Функция

extern int atoi(char*);

функция atoi() это стандартная библиотечная функция для преобразования представления целого в виде строки в его внуреннюю (двоичную) форму. Случайные числа генерируются с пмощью стандартной функции rand():

extern int rand(); // Не очень случайные, будьте осторожны

int randint(int u) // в диапазоне 1..u (* int r = rand(); if (r « 0) r = -r; return 1 + r%u ; *)

Подробности реализации класса должны представлять для пользователя весьма незначительный интерес, но здесь в любом случае будут функции члены. Конструктор выделяет целый вектор заданного максимального размера множества, а деструктор освбождает его:

intset::intset(int m, int n)//самое большее,m int'ов в 1..n (* if (m«1 !! n„m) error(«недопустимый размер intset“); cursize = 0; maxsize = m; x = new int[maxsize]; *)

intset::~intset() (* delete x; *)

Целые числа вставляются, поэтому они хранятся в возратающем порядке:

void intset::insert(int t) (* if (++cursize » maxsize) error(«слишком много элементов»); int i = cursize-1; x[i] = t;

while (i»0 amp; amp; x[i-1]»x[i]) (* int t = x[i]; // переставить x[i] и [i-1] x[i] = x[i-1]; x[i-1] = t; i–; *) *)

Для нахождения членов используется просто двоичный писк:

int intset::member(int t) // двоичный поиск (* int l = 0; int u = cursize-1;

while (l «= u) (* int m = (l+u)/2; if (t „ x[m]) u = m-1; else if (t “ x[m]) l = m+1; else return 1; // найдено *) return 0; // не найдено *)

И, наконец, нам нужно обеспечить множество операций, чтобы пользователь мог осуществлять цикл по множеству в нектором порядке, поскольку представление intset от пользователя скрыто. Множество внутренней упорядоченности не имеет, поэтму мы не можем просто дать возможность обращаться к вектору (завтра я, наверное, реализую intset по-другому, в виде свзанного списка).

Дается три функции: iterate() для инициализации итерции, ok() для проверки, есть ли следующий элемент, и next() для того, чтобы взять следующий элемент:

class intset (* // ... void iterate(int amp; i) (* i = 0; *) int ok(int amp; i) (* return i«cursize; *) int next(int amp; i) (* return x[i++]; *) *);

Чтобы дать возможность этим трем операциям работать соместно и чтобы запомнить, куда дошел цикл, пользователь дожен дать целый параметр. Поскольку элементы хранятся в отсотированном списке, их реализация тривиальна. Теперь можно определить функцию печати по порядку print_in_order: