Интерфейсы и Реализации

<!--StartFragment -->
  • Альтернативные Реализации

  • Законченный Класс

Что представляет собой хороший класс? Нечто, имеющее небольшое и хорошо определенное множество действий. Нечто, что можно рассматривать как \"черный ящик\", которым манипулируют только посредством этого множества действий. Нечто, чье фактическое представление можно любым мыслимым способом изменить, не повлияв на способ использования множества действий. Нечто, чего можно хотеть иметь больше одного.

Для всех видов контейнеров существуют очевидные примеры: таблицы, множества, списки, вектора, словари и т.д. Такой класс имеет операцию \"вставить\", обычно он также имеет операции для проверки того, был ли вставлен данный элемент. В нем могут быть действия для осуществления проверки всех элементов в определенном порядке, и кроме всего прочего, в нем может иметься операция для удаления элемента. Обычно контейнерные (то есть, вмещающие) классы имеют конструкторы и деструкторы.

Скрытие данных и продуманный интерфейс может дать концепция модуля . Класс, однако, является типом. Чтобы использовать его, необходимо создать объекты этого класса, и таких объектов можно создавать столько, сколько нужно. Модуль же сам является объектом. Чтобы использовать его, его надо только инициализировать, и таких объектов ровно один.

Альтернативные Реализации

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


struct name {
char* string;
char* next;
double value;
};



Вот вариант класса table:


// файл table.h

class table {
name* tbl;
public:
table() { tbl = 0; }


name* look(char*, int = 0);
name* insert(char* s) { return look(s,1); }
};


Эта таблица отличается от той, которая определена в Главе 3 тем, что это настоящий тип. Можно описать более чем одну table, можно иметь указатель на table и т.д.

Например:


#include \"table.h\"

table globals;
table keywords;
table* locals;


main() {
locals = new table;
// ...
}


Вот реализация table::look(), которая использует линейный поиск в связанном списке имен name в таблице:


#include


name* table::look(char* p, int ins)
{
for (name* n = tbl; 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;
tbl = nn;
return nn;
}


Теперь рассмотрим класс table, усовершенствованный таким образом, чтобы использовать хэшированный просмотр, как это делалось в примере с настольным калькулятором. Сделать это труднее из-за того ограничения, что уже написанные программы, в которых использовалась только что определенная версия класса table, должны оставаться верными без изменений:


class table {
name** tbl;
int size;
public:
table(int sz = 15);
~table();


name* look(char*, int = 0);
name* insert(char* s) { return look(s,1); }
};


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


table::table(int sz)
{
if (sz < 0) error(\"отрицательный размер таблицы\");
tbl = new name*[size=sz];
for (int i = 0; inext) {
delete n->string;
delete n;
}
delete tbl;
}


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


#include

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;
}


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

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

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

Законченный Класс

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

Вот пример законченного типа 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& i) { i = 0; }
int ok(int& i) { return i


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 maxsize) error("слищком много элементов");
int i = cursize-1;
x[i] = t;


while (i>0 && 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& i) { i = 0; }
int ok(int& i) { return iiterate(var);
while (set->ok(var)) cout << set->next(var) << "\\n";
}



Опубликовал admin
23 Мар, Вторник 2004г.



Программирование для чайников.