Бьерн Страуструп - Язык программирования С++. Главы 5-7 - Законченный пример класса
ОГЛАВЛЕНИЕ
Страница 12 из 70
5.3.2 Законченный пример класса
Программирование без упрятывания данных (в расчете на структуры) требует меньшего предварительного обдумывания задачи, чем программирование с упрятыванием данных (в расчете на классы). Структуру можно определить не очень задумываясь о том, как ее будут использовать. Когда определяется класс, внимание концентрируется на том, чтобы обеспечить для нового типа полный набор операций. Это важное смещение акцента в проектировании программ. Обычно время, затраченное на разработку нового типа, многократно окупается в процессе отладки и развития программы.Вот пример законченного определения типа intset, представляющего понятие "множество целых":
class intset {Для проверки этого класса вначале создадим, а затем распечатаем множество случайных целых чисел. Это простое множество целых можно использовать для проверки, есть ли повторения в их последовательности. Но для большинства задач нужен, конечно, более развитый тип множества. Как всегда возможны ошибки, поэтому нужна функция:
int cursize, maxsize;
int *x;
public:
intset(int m, int n); // не более m целых из 1..n
~intset();
int member(int t) const; // является ли t членом?
void insert(int t); // добавить к множеству t
void start(int& i) const { i = 0; }
void ok(int& i) const { return i<cursize; }
void next(int& i) const { return x[i++]; }
};
#include <iostream.h>Класс intset используется в функции main(), для которой должно быть задано два параметра: первый определяет число создаваемых случайных чисел, а второй - диапазон их значений:
void error(const char *s)
{
cerr << "set: " << s << '\n';
exit(1);
}
int main(int argc, char* argv[])Значение счетчика параметров программы argc равно 3, хотя программа имеет только два параметра. Дело в том, что в argv[0] всегда передается дополнительный параметр, содержащий имя программы. Функция
{
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(&s);
}
extern "C" int atoi(const char*)является стандартной библиотечной функцией, преобразующей целое из строкового представления во внутреннюю двоичную форму. Как обычно, если вы не хотите иметь такое описание в своей программе, то вам надо включить в нее соответствующий заголовочный файл, содержащий описания стандартных библиотечных функций. Случайные числа генерируются с помощью стандартной функции rand:
extern "C" 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 целых в 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 && x[i-1]>x[i]) {
int t = x[i]; // поменять местами x[i] и x[i-1]
x[i] = x[i-1];
x[i-1] = t;
i--;
}
}
int intset::member(int t) const // двоичный поискНаконец, нужно предоставить пользователю набор операций, с помощью которых он мог бы организовать итерацию по множеству в некотором порядке (ведь порядок, используемый в представлении intset, от него скрыт). Множество по своей сути не является внутренне упорядоченным, и нельзя позволить просто выбирать элементы массива (а вдруг завтра intset будет реализовано в виде связанного списка?).
{
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; // не найден
}
Пользователь получает три функции: start() - для инициализации итерации, ok() - для проверки, есть ли следующий элемент, и next() - для получения следующего элемента:
class intset {Чтобы обеспечить совместную работу этих трех операций, надо запоминать тот элемент, на котором остановилась итерация. Для этого пользователь должен задавать целый параметр. Поскольку наше представление множества упорядоченное, реализация этих операций тривиальна. Теперь можно определить функцию print_in_order:
// ...
void start(int& i) const { i = 0; }
int ok(int& i) const { return i<cursize; }
int next(int& i) const { return x[i++]; }
};
void print_in_order(intset* set)Другой способ построения итератора по множеству приведен в $$7.8.
{
int var;
set->sart(var);
while (set->ok(var)) cout << set->next(var) << '\n';
}