Страница:
как позиция 3 для клавиши 2, то соответствующая команда реализуется
вызовом:
(*button2[3])();
Чтобы полностью оценить мощность конструкции указатель на функцию,
стоит попытаться написать программу без нее. Меню можно изменять
в динамике, если добавлять новые функции в таблицу команд.
Довольно просто создавать в динамике и новые меню.
Указатели на функции помогают реализовать полиморфические
подпрограммы, т.е. такие подпрограммы, которые можно применять
к объектам различных типов:
typedef int (*CFT)(void*,void*);
void sort(void* base, unsigned n, unsigned int sz, CFT cmp)
/*
Сортировка вектора "base" из n элементов
в возрастающем порядке;
используется функция сравнения, на которую указывает cmp.
Размер элементов равен "sz".
Алгоритм очень неэффективный: сортировка пузырьковым методом
*/
{
for (int i=0; i<n-1; i++)
for (int j=n-1; i<j; j--) {
char* pj = (char*)base+j*sz; // b[j]
char* pj1 = pj - sz; // b[j-1]
if ((*cmp)(pj,pj1) < 0) {
// поменять местами b[j] и b[j-1]
for (int k = 0; k<sz; k++) {
char temp = pj[k];
pj[k] = pj1[k];
pj1[k] = temp;
}
}
}
}
В подпрограмме sort неизвестен тип сортируемых объектов; известно
только их число (размер массива), размер каждого элемента и функция,
которая может сравнивать объекты. Мы выбрали для функции sort()
такой же заголовок, как у qsort() - стандартной функции сортировки
из библиотеки С. Эту функцию используют настоящие программы.
Покажем, как с помощью sort() можно отсортировать таблицу с такой
структурой:
struct user {
char* name; // имя
char* id; // пароль
int dept; // отдел
};
typedef user* Puser;
user heads[] = {
"Ritchie D.M.", "dmr", 11271,
"Sethi R.", "ravi", 11272,
"SZYmanski T.G.", "tgs", 11273,
"Schryer N.L.", "nls", 11274,
"Schryer N.L.", "nls", 11275
"Kernighan B.W.", "bwk", 11276
};
void print_id(Puser v, int n)
{
for (int i=0; i<n; i++)
cout << v[i].name << '\t'
<< v[i].id << '\t'
<< v[i].dept << '\n';
}
Чтобы иметь возможность сортировать, нужно вначале определить
подходящие функции сравнения. Функция сравнения должна возвращать
отрицательное число, если ее первый параметр меньше второго,
нуль, если они равны, и положительное число в противном случае:
int cmp1(const void* p, const void* q)
// сравнение строк, содержащих имена
{
return strcmp(Puser(p)->name, Puser(q)->name);
}
int cmp2(const void* p, const void* q)
// сравнение номеров разделов
{
return Puser(p)->dept - Puser(q)->dept;
}
Следующая программа сортирует и печатает результат:
int main()
{
sort(heads,6,sizeof(user), cmp1);
print_id(heads,6); // в алфавитном порядке
cout << "\n";
sort(heads,6,sizeof(user),cmp2);
print_id(heads,6); // по номерам отделов
}
Допустима операция взятия адреса и для функции-подстановки, и для
перегруженной функции ($$R.13.3).
Отметим, что неявное преобразование указателя на что-то в
указатель типа void* не выполняется для параметра функции, вызываемой
через указатель на нее. Поэтому функцию
int cmp3(const mytype*, const mytype*);
нельзя использовать в качестве параметра для sort().
Поступив иначе, мы нарушаем заданное в описании условие, что
cmp3() должна вызываться с параметрами типа mytype*. Если вы
специально хотите нарушить это условие, то должны использовать
явное преобразование типа.
Макросредства языка определяются в $$R.16. В С++ они играют гораздо
меньшую роль, чем в С. Можно даже дать такой совет: используйте
макроопределения только тогда, когда не можете без них обойтись.
Вообще говоря, считается, что практически каждое появление
макроимени является свидетельством некоторых недостатков
языка, программы или программиста. Макросредства создают определенные
трудности для работы служебных системных программ, поскольку
они перерабатывают программный текст еще до трансляции. Поэтому, если
ваша программа использует макросредства,
то сервис, предоставляемый такими программами, как отладчик,
профилировщик, программа перекрестных ссылок, будет для нее
неполным. Если все-таки вы решите использовать
макрокоманды, то вначале тщательно изучите описание препроцессора
С++ в вашем справочном руководстве и не старайтесь быть слишком умным.
Простое макроопределение имеет вид:
#define имя остаток-строки
В тексте программы лексема имя заменяется на остаток-строки. Например,
объект = имя
будет заменено на
объект = остаток-строки
Макроопределение может иметь параметры. Например:
#define mac(a,b) argument1: a argument2: b
В макровызове mac должны быть заданы две строки, представляющие
параметры. При подстановке они заменят a и b в макроопределении
mac(). Поэтому строка
expanded = mac(foo bar, yuk yuk)
при подстановке преобразуется в
expanded = argument1: foo bar argument2: yuk yuk
Макроимена нельзя перегружать. Рекурсивные макровызовы ставят
перед препроцессором слишком сложную задачу:
// ошибка:
#define print(a,b) cout<<(a)<<(b)
#define print(a,b,c) cout<<(a)<<(b)<<(c)
// слишком сложно:
#define fac(n) (n>1) ?n*fac(n-1) :1
Препроцессор работает со строками и практически ничего не знает о
синтаксисе C++, типах языка и областях видимости. Транслятор
имеет дело только с уже раскрытым макроопределением, поэтому
ошибка в нем может диагностироваться уже после подстановки, а не при
определении макроимени. В результате появляются довольно путанные
сообщения об ошибках.
Допустимы такие макроопределения:
#define Case break;case
#define forever for(;;)
А вот совершенно излишние макроопределения:
#define PI 3.141593
#define BEGIN {
#define END }
Следующие макроопределения могут привести к ошибкам:
#define SQUARE(a) a*a
#define INCR_xx (xx)++
#define DISP = 4
Чтобы убедиться в этом, достаточно попробовать сделать подстановку
в таком примере:
int xx = 0; // глобальный счетчик
void f() {
int xx = 0; // локальная переменная
xx = SQUARE(xx+2); // xx = xx +2*xx+2;
INCR_xx; // увеличивается локальная переменная xx
if (a-DISP==b) { // a-=4==b
// ...
}
}
При ссылке на глобальные имена в макроопределении используйте операцию
разрешения области видимости ($$2.1.1), и всюду, где это возможно,
заключайте имя параметра макроопределения в скобки. Например:
#define MIN(a,b) (((a)<(b))?(a):(b))
Если макроопределение достаточно сложное, и требуется комментарий
к нему, то разумнее написать комментарий вида /* */, поскольку
в реализации С++ может использоваться препроцессор С, который не
распознает комментарии вида //. Например:
#define m2(a) something(a) /* глубокомысленный комментарий */
С помощью макросредств можно создать свой собственный язык,
правда, скорее всего, он будет непонятен другим. Кроме того, препроцессор
С предоставляет довольно слабые макросредства. Если ваша задача
нетривиальна, вы, скорее всего, обнаружите, что решить ее с помощью этих
средств либо невозможно, либо чрезвычайно трудно. В качестве
альтернативы традиционному использованию макросредств в язык введены
конструкции const, inline и шаблоны типов. Например:
const int answer = 42;
template<class T>
inline T min(T a, T b) { return (a<b)?a:b; }
1. (*1) Составьте следующие описания: функция с параметрами типа
указатель на символ и ссылка на целое, невозвращающая значения;
указатель на такую функцию; функция с параметром, имеющим тип
такого указателя; функция, возвращающая такой указатель. Напишите
определение функции, у которой параметр и возвращаемое значение
имеют тип такого указателя. Подсказка: используйте typedef.
2. (*1) Как понимать следующее описание? Где оно может пригодиться?
typedef int (rifii&) (int, int);
3. (*1.5) Напишите программу, подобную той, что выдает "Hello, world".
Она получает имя (name) как параметр командной строки и выдает
"Hello, name". Измените программу так, чтобы она получала
произвольное число имен и всем им выдавала свое приветствие:
"Hello, ...".
4. (1.5) Напишите программу, которая, беря из командной строки
произвольное число имен файлов, все эти файлы переписывает
один за другим в cout. Поскольку в программе происходит
конкатенация файлов, вы можете назвать ее cat от слова
concatenation - конкатенация).
5. (*2) Переведите небольшую программу с языка С на С++. Измените
заголовочные файлы так, чтобы они содержали описание всех
вызываемых функций и описание типов всех параметров. По возможности
все команды #define замените конструкциями enum, const или
inline. Удалите из файлов .c все описания внешних, а определения
функций приведите к виду, соответствующему С++. Вызовы malloc() и
free() замените операциями new и delete. Удалите ненужные операции
приведения.
6. (*2) Напишите функцию sort() ($$4.6.9), использующую более
эффективный алгоритм сортировки.
7. (*2) Посмотрите на определение структуры tnode в $$R.9.3. Напишите
функцию, заносящую новые слова в дерево узлов tnode. Напишите
функцию для вывода узлов дерева tnode. Напишите функцию,
которая производит такой вывод в алфавитном порядке.
Измените структуру tnode так, чтобы в ней содержался
только указатель на слово произвольной длины, которое размещается
с помощью new в свободной памяти. Измените функцию так, чтобы
она работала с новой структурой tnode.
8. (*1) Напишите функцию itoa(), которая использовалась в примере
из $$4.6.8.
9. (*2) Узнайте, какие стандартные заголовочные файлы есть в вашей
системе. Поройтесь в каталогах /usr/include или /usr/include/CC
(или в тех каталогах, где хранятся стандартные заголовочные
файлы вашей системы). Прочитайте любой показавшийся интересным
файл.
10. (*2) Напишите функцию, которая будет переворачивать двумерный
массив. (Первый элемент массива станет последним).
11. (*2) Напишите шифрующую программу, которая читает символы из
cin и пишет их в cout в зашифрованном виде. Можно использовать
следующий простой метод шифрации: для символа s зашифрованное
представление получается в результате операции s^key[i], где
key - массив символов, передаваемый в командной строке. Символы
из массива key используются в циклическом порядке, пока не будет
прочитан весь входной поток. Первоначальный текст получается
повторным применением той же операции с теми же элементами key.
Если массив key не задан (или задана пустая строка), шифрация не
происходит.
12. (*3) Напишите программу, которая помогает дешифрировать текст,
зашифрованный описанным выше способом, когда ключ (т.е. массив
key) неизвестен. Подсказка: см. D Kahn "The Codebreakers",
Macmillan, 1967, New York, стр. 207-213.
13. (*3) Напишите функцию обработки ошибок, первый параметр который
подобен форматирующей строке-параметру printf() и содержит форматы
%s, %c и %d. За ним может следовать произвольное количество
числовых параметров. Функцию printf() не используйте. Если смысл
формата %s и других форматов вам неизвестен, обратитесь к $$10.6.
Используйте <stdarg.h>.
14. (*1) Какое имя вы выбрали бы для типов указателей на функции,
которые определяются с помощью typedef?
15. (*2) Исследуйте разные программы, чтобы получить представление
о разных используемых на практике стилях именования. Как
используются заглавные буквы? Как используется подчерк? В каких
случаях используются такие имена, как i или x?
16. (*1) Какие ошибки содержатся в следующих макроопределениях?
#define PI = 3.141593;
#define MAX(a,b) a>b?a:b
#define fac(a) (a)*fac((a)-1)
17. (*3) Напишите макропроцессор с простыми возможностями, как у
препроцессора С. Текст читайте из cin, а результат записывайте
в cout. Вначале реализуйте макроопределения без параметров.
Подсказка: в программе калькулятора есть таблица имен и
синтаксический анализатор, которыми можно воспользоваться.
18. (*2) Напишите программу, извлекающую квадратный корень из двух (2)
с помощью стандартной функции sqrt(), но не включайте в программу
<math.h>. Сделайте это упражнение с помощью функции sqrt()
на Фортране.
19. (*2) Реализуйте функцию print() из $$4.6.7.
"Эти типы не абстрактные, они столь же реальны,
как int и float"
- Даг Макилрой
В этой главе описываются возможности определения новых типов,
для которых доступ к данным ограничен заданным множеством
функций, осуществляющих его. Объясняется, как можно использовать
члены структуры данных, как ее защищать, инициализировать и,
наконец, уничтожать. В примерах приведены простые классы для
управления таблицей имен, работы со стеком, множеством и
реализации дискриминирующего (т.е. надежного) объединения.
Следующие три главы завершают описание возможностей С++ для
построения новых типов, и в них содержится больше интересных
примеров.
Понятие класса, которому посвящена эта и три следующих главы, служит
в С++ для того, чтобы дать программисту инструмент построения новых
типов. Ими пользоваться не менее удобно, чем встроенными.
В идеале использование определенного пользователем типа не должно
отличаться от использования встроенных типов. Различия возможны только
в способе построения.
Тип есть вполне конкретное представление некоторого понятия.
Например, в С++ тип float с операциями +, -, * и т.д. является
хотя и ограниченным, но конкретным представлением математического
понятия вещественного числа. Новый тип создается для того, чтобы
стать специальным и конкретным представлением понятия, которое не находит
прямого и естественного отражения среди встроенных типов. Например,
в программе из области телефонной связи можно ввести тип
trunk_module (линия-связи), в видеоигре - тип explosion (взрыв),
а в программе, обрабатывающей текст, - тип list_of_paragraphs
(список-параграфов). Обычно проще понимать и изменять программу,
в которой типы хорошо представляют используемые в задаче понятия.
Удачно подобранное множество пользовательских типов делает программу
более ясной. Оно позволяет транслятору обнаруживать недопустимое
использование объектов, которое в противном случае останется
невыявленным до отладки программы.
Главное в определении нового типа - это отделить несущественные
детали реализации (например, расположение данных в объекте нового
типа) от тех его характеристик, которые существенны для правильного
его использования (например, полный список функций, имеющих доступ
к данным). Такое разделение обеспечивается тем, что вся работа со
структурой данных и внутрение, служебные операции над нею доступны
только через специальный интерфейс (через "одно горло").
Глава состоит из четырех частей:
$$5.2 Классы и члены. Здесь вводится основное понятие
пользовательского типа, называемого классом. Доступ к объектам
класса может ограничиваться множеством функций, описания
которых входят в описание класса. Эти функции называются
функциями-членами и друзьями. Для создания объектов класса
используются специальные функции-члены, называемые
конструкторами. Можно описать специальную функцию-член
для удаления объектов класса при его уничтожении. Такая
функция называется деструктором.
$$5.3 Интерфейсы и реализации. Здесь приводятся два примера
разработки, реализации и использования классов.
$$5.4 Дополнительные свойства классов. Здесь приводится много
дополнительных подробностей о классах. Показано, как
функции, не являющейся членом класса, предоставить доступ
к его частной части. Такую функцию называют другом класса.
Вводятся понятия статических членов класса и указателей
на члены класса. Здесь же показано, как определить
дискриминирующее объединение.
$$5.5 Конструкторы и деструкторы. Объект может создаваться как
автоматический, статический или как объект в свободной
памяти. Кроме того, объект может быть членом некоторого
агрегата (массива или другого класса), который тоже
можно размещать одним из этих трех способов. Подробно
объясняется использование конструкторов и деструкторов,
описывается применение определяемых пользователем функций
размещения в свободной памяти и функций освобождения памяти.
Класс - это пользовательский тип. Этот раздел знакомит с основными
средствами определения класса, создания его объектов, работы с
такими объектами и, наконец, удаления этих объектов после
использования.
Посмотрим, как можно представить в языке понятие даты, используя
для этого тип структуры и набор функций, работающих с переменными
этого типа:
struct date { int month, day, year; };
date today;
void set_date(date*, int, int, int);
void next_date(date*);
void print_date(const date*);
// ...
Никакой явной связи между функциями и структурой date нет. Ее можно
установить, если описать функции как члены структуры:
struct date {
int month, day, year;
void set(int, int, int);
void get(int*, int* int*);
void next();
void print();
};
Описанные таким образом функции называются функциями-членами. Их можно
вызывать только через переменные соответствующего типа, используя
стандартную запись обращения к члену структуры:
date today;
date my_birthday;
void f()
{
my_birthday.set(30,12,1950);
today.set(18,1,1991);
my_birthday.print();
today.next();
}
Поскольку разные структуры могут иметь функции-члены с одинаковыми
именами, при определении функции-члена нужно указывать имя структуры:
void date::next()
{
if (++day > 28 ) {
// здесь сложный вариант
}
}
В теле функции-члена имена членов можно использовать без указания
имени объекта. В таком случае имя относится к члену того объекта,
для которого была вызвана функция.
Мы определили несколько функций для работы со структурой date, но из ее
описания не следует, что это единственные функции, которые
предоставляют доступ к объектам типа date. Можно установить такое
ограничение, описав класс вместо структуры:
class date {
int month, day, year;
public:
void set(int, int, int);
void get(int*, int*, int*);
void next();
void print()
};
Служебное слово public (общий) разбивает описание класса на две части.
Имена, описанные в первой частной (private) части класса, могут
использоваться только в функциях-членах. Вторая - общая часть -
представляет собой интерфейс с объектами класса. Поэтому структура - это
такой класс, в котором по определению все члены являются общими.
Функции-члены класса определяются и используются точно так же, как
было показано в предыдущем разделе:
void date::print() // печать даты в принятом в США виде
{
cout << month << '/' << day << '/' << year ;
}
Однако от функций не членов частные члены класса date уже ограждены:
void backdate()
{
today.day--; // ошибка
}
Есть ряд преимуществ в том, что доступ к структуре данных ограничен
явно указанным списком функций. Любая ошибка в дате (например,
December, 36, 1985) могла быть внесена только функцией-членом,
поэтому первая стадия отладки - локализация ошибки - происходит
даже до первого пуска программы. Это только частный случай общего
правила: любое изменение в поведении типа date может и должно
вызываться изменениями в его членах. Другое преимущество в том, что
потенциальному пользователю класса для работы с ним достаточно
знать только определения функций-членов.
Защита частных данных основывается только на ограничении
использования имен членов класса. Поэтому ее можно обойти с
помощью манипуляций с адресами или явных преобразований типа,
но это уже можно считать мошенничеством.
В функции-члене можно непосредственно использовать имена членов
того объекта, для которого она была вызвана:
class X {
int m;
public:
int readm() { return m; }
};
void f(X aa, X bb)
{
int a = aa.readm();
int b = bb.readm();
// ...
}
При первом вызове readm() m обозначает aa.m, а при втором - bb.m.
У функции-члена есть дополнительный скрытый параметр, являющийся
указателем на объект, для которого вызывалась функция. Можно явно
использовать этот скрытый параметр под именем this. Считается, что
в каждой функции-члене класса X указатель this описан неявно как
X *const this;
и инициализируется, чтобы указывать на объект, для которого
функция-член вызывалась. Этот указатель нельзя изменять, поскольку
он постоянный (*const). Явно описать его тоже нельзя, т.к. this -
это служебное слово. Можно дать эквивалентное описание класса X:
class X {
int m;
public:
int readm() { return this->m; }
};
Для обращения к членам использовать this излишне. В основном this
используется в функциях-членах, непосредственно работающих с
указателями. Типичный пример - функция, которая вставляет элемент
в список с двойной связью:
class dlink {
dlink* pre; // указатель на предыдущий элемент
dlink* suc; // указатель на следующий элемент
public:
void append(dlink*);
// ...
};
void dlink::append(dlink* p)
{
p->suc = suc; // т.е. p->suc = this->suc
p->pre = this; // явное использование "this"
suc->pre = p; // т.е. this->suc->pre = p
suc = p; // т.е. this->suc = p
}
dlink* list_head;
void f(dlink* a, dlink* b)
{
// ...
list_head->append(a);
list_head->append(b);
}
Списки с такой общей структурой служат фундаментом списочных классов,
описываемых в главе 8. Чтобы присоединить звено к списку, нужно
изменить объекты, на которые настроены указатели this, pre и suc.
Все они имеют тип dlink, поэтому функция-член dlink::append() имеет
к ним доступ. Защищаемой единицей в С++ является класс, а не отдельный
объект класса.
Можно описать функцию-член таким образом, что объект, для которого
она вызывается, будет доступен ей только по чтению. Тот факт, что
функция не будет изменять объект, для которого она вызывается
(т.е. this*), обозначается служебным словом const в конце списка
параметров:
class X {
int m;
public:
readme() const { return m; }
writeme(int i) { m = i; }
};
Функцию-член со спецификацией const можно вызывать для постоянных
объектов, а функцию-член без такой спецификации - нельзя:
void f(X& mutable, const X& constant)
{
mutable.readme(); // нормально
mutable.writeme(7); // нормально
constant.readme(); // нормально
constant.writeme(7); // ошибка
}
В этом примере разумный транслятор смог бы обнаружить, что
функция X::writeme() пытается изменить постоянный объект. Однако,
это непростая задача для транслятора. Из-за раздельной
трансляции он в общем случае не может гарантировать "постоянство"
объекта, если нет соответствующего описания со спецификацией
const. Например, определения readme() и writeme() могли быть в
другом файле:
class X {
int m;
public:
readme() const;
writeme(int i);
};
В таком случае описание readme() со спецификацией const существенно.
Тип указателя this в постоянной функции-члене класса X есть
const X *const. Это значит, что без явного приведения с помощью this
нельзя изменить значение объекта:
class X {
int m;
public:
// ...
void implicit_cheat() const { m++; } // ошибка
void explicit_cheat() const { ((X*)this)->m++; }
// нормально
};
Отбросить спецификацию const можно потому, что понятие
"постоянства" объекта имеет два значения. Первое, называемое
"физическим постоянством" состоит в том, что объект хранится
в защищенной от записи памяти. Второе, называемое "логическим
постоянством" заключается в том, что объект выступает как
постоянный (неизменяемый) по отношению к пользователям. Операция
над логически постоянным объектом может изменить часть данных
объекта, если при этом не нарушается его постоянство
с точки зрения пользователя. Операциями, ненарушающими логическое
постоянство объекта, могут быть буферизация значений, ведение
статистики, изменение переменных-счетчиков в постоянных
функциях-членах.
Логического постоянства можно достигнуть приведением, удаляющим
спецификацию const:
class calculator1 {
int cache_val;
int cache_arg;
// ...
public:
int compute(int i) const;
// ...
};
int calculator1::compute(int i) const
{
if (i == cache_arg) return cache_val;
// нелучший способ
((calculator1*)this)->cache_arg = i;
((calculator1*)this)->cache_val = val;
return val;
}
Этого же результата можно достичь, используя указатель на данные
без const:
struct cache {
int val;
int arg;
};
class calculator2 {
cache* p;
// ...
public:
int compute(int i) const;
// ...
};
int calculator2::compute(int i) const
{
if (i == p->arg) return p->val;
// нелучший способ
p->arg = i;
p->val = val;
return val;
}
Отметим, что const нужно указывать как в описании, так и в определении
постоянной функции-члена. Физическое постоянство обеспечивается
помещением объекта в защищенную по записи память, только если в классе
нет конструктора ($$7.1.6).
Инициализация объектов класса с помощью таких функций как set_date()
- неэлегантное и чреватое ошибками решение. Поскольку явно не было
указано, что объект требует инициализации, программист может либо забыть
это сделать, либо сделать дважды, что может привести к столь же
катастрофическим последствиям. Лучше дать программисту возможность
описать функцию, явно предназначенную для инициализации объектов.
Поскольку такая функция конструирует значение данного типа, она
называется конструктором. Эту функцию легко распознать - она имеет
то же имя, что и ее класс:
class date {
// ...
date(int, int, int);
};
Если в классе есть конструктор, все объекты этого класса будут
проинициализированы. Если конструктору требуются параметры, их
надо указывать:
date today = date(23,6,1983);
date xmas(25,12,0); // краткая форма
date my_birthday; // неправильно, нужен инициализатор
Часто бывает удобно указать несколько способов инициализации
объекта. Для этого нужно описать несколько конструкторов:
class date {
int month, day, year;
public:
// ...
date(int, int, int); // день, месяц, год
date(int, int); // день, месяц и текущий год
date(int); // день и текущие год и месяц
date(); // стандартное значение: текущая дата
date(const char*); // дата в строковом представлении
};
Параметры конструкторов подчиняются тем же правилам о типах
вызовом:
(*button2[3])();
Чтобы полностью оценить мощность конструкции указатель на функцию,
стоит попытаться написать программу без нее. Меню можно изменять
в динамике, если добавлять новые функции в таблицу команд.
Довольно просто создавать в динамике и новые меню.
Указатели на функции помогают реализовать полиморфические
подпрограммы, т.е. такие подпрограммы, которые можно применять
к объектам различных типов:
typedef int (*CFT)(void*,void*);
void sort(void* base, unsigned n, unsigned int sz, CFT cmp)
/*
Сортировка вектора "base" из n элементов
в возрастающем порядке;
используется функция сравнения, на которую указывает cmp.
Размер элементов равен "sz".
Алгоритм очень неэффективный: сортировка пузырьковым методом
*/
{
for (int i=0; i<n-1; i++)
for (int j=n-1; i<j; j--) {
char* pj = (char*)base+j*sz; // b[j]
char* pj1 = pj - sz; // b[j-1]
if ((*cmp)(pj,pj1) < 0) {
// поменять местами b[j] и b[j-1]
for (int k = 0; k<sz; k++) {
char temp = pj[k];
pj[k] = pj1[k];
pj1[k] = temp;
}
}
}
}
В подпрограмме sort неизвестен тип сортируемых объектов; известно
только их число (размер массива), размер каждого элемента и функция,
которая может сравнивать объекты. Мы выбрали для функции sort()
такой же заголовок, как у qsort() - стандартной функции сортировки
из библиотеки С. Эту функцию используют настоящие программы.
Покажем, как с помощью sort() можно отсортировать таблицу с такой
структурой:
struct user {
char* name; // имя
char* id; // пароль
int dept; // отдел
};
typedef user* Puser;
user heads[] = {
"Ritchie D.M.", "dmr", 11271,
"Sethi R.", "ravi", 11272,
"SZYmanski T.G.", "tgs", 11273,
"Schryer N.L.", "nls", 11274,
"Schryer N.L.", "nls", 11275
"Kernighan B.W.", "bwk", 11276
};
void print_id(Puser v, int n)
{
for (int i=0; i<n; i++)
cout << v[i].name << '\t'
<< v[i].id << '\t'
<< v[i].dept << '\n';
}
Чтобы иметь возможность сортировать, нужно вначале определить
подходящие функции сравнения. Функция сравнения должна возвращать
отрицательное число, если ее первый параметр меньше второго,
нуль, если они равны, и положительное число в противном случае:
int cmp1(const void* p, const void* q)
// сравнение строк, содержащих имена
{
return strcmp(Puser(p)->name, Puser(q)->name);
}
int cmp2(const void* p, const void* q)
// сравнение номеров разделов
{
return Puser(p)->dept - Puser(q)->dept;
}
Следующая программа сортирует и печатает результат:
int main()
{
sort(heads,6,sizeof(user), cmp1);
print_id(heads,6); // в алфавитном порядке
cout << "\n";
sort(heads,6,sizeof(user),cmp2);
print_id(heads,6); // по номерам отделов
}
Допустима операция взятия адреса и для функции-подстановки, и для
перегруженной функции ($$R.13.3).
Отметим, что неявное преобразование указателя на что-то в
указатель типа void* не выполняется для параметра функции, вызываемой
через указатель на нее. Поэтому функцию
int cmp3(const mytype*, const mytype*);
нельзя использовать в качестве параметра для sort().
Поступив иначе, мы нарушаем заданное в описании условие, что
cmp3() должна вызываться с параметрами типа mytype*. Если вы
специально хотите нарушить это условие, то должны использовать
явное преобразование типа.
Макросредства языка определяются в $$R.16. В С++ они играют гораздо
меньшую роль, чем в С. Можно даже дать такой совет: используйте
макроопределения только тогда, когда не можете без них обойтись.
Вообще говоря, считается, что практически каждое появление
макроимени является свидетельством некоторых недостатков
языка, программы или программиста. Макросредства создают определенные
трудности для работы служебных системных программ, поскольку
они перерабатывают программный текст еще до трансляции. Поэтому, если
ваша программа использует макросредства,
то сервис, предоставляемый такими программами, как отладчик,
профилировщик, программа перекрестных ссылок, будет для нее
неполным. Если все-таки вы решите использовать
макрокоманды, то вначале тщательно изучите описание препроцессора
С++ в вашем справочном руководстве и не старайтесь быть слишком умным.
Простое макроопределение имеет вид:
#define имя остаток-строки
В тексте программы лексема имя заменяется на остаток-строки. Например,
объект = имя
будет заменено на
объект = остаток-строки
Макроопределение может иметь параметры. Например:
#define mac(a,b) argument1: a argument2: b
В макровызове mac должны быть заданы две строки, представляющие
параметры. При подстановке они заменят a и b в макроопределении
mac(). Поэтому строка
expanded = mac(foo bar, yuk yuk)
при подстановке преобразуется в
expanded = argument1: foo bar argument2: yuk yuk
Макроимена нельзя перегружать. Рекурсивные макровызовы ставят
перед препроцессором слишком сложную задачу:
// ошибка:
#define print(a,b) cout<<(a)<<(b)
#define print(a,b,c) cout<<(a)<<(b)<<(c)
// слишком сложно:
#define fac(n) (n>1) ?n*fac(n-1) :1
Препроцессор работает со строками и практически ничего не знает о
синтаксисе C++, типах языка и областях видимости. Транслятор
имеет дело только с уже раскрытым макроопределением, поэтому
ошибка в нем может диагностироваться уже после подстановки, а не при
определении макроимени. В результате появляются довольно путанные
сообщения об ошибках.
Допустимы такие макроопределения:
#define Case break;case
#define forever for(;;)
А вот совершенно излишние макроопределения:
#define PI 3.141593
#define BEGIN {
#define END }
Следующие макроопределения могут привести к ошибкам:
#define SQUARE(a) a*a
#define INCR_xx (xx)++
#define DISP = 4
Чтобы убедиться в этом, достаточно попробовать сделать подстановку
в таком примере:
int xx = 0; // глобальный счетчик
void f() {
int xx = 0; // локальная переменная
xx = SQUARE(xx+2); // xx = xx +2*xx+2;
INCR_xx; // увеличивается локальная переменная xx
if (a-DISP==b) { // a-=4==b
// ...
}
}
При ссылке на глобальные имена в макроопределении используйте операцию
разрешения области видимости ($$2.1.1), и всюду, где это возможно,
заключайте имя параметра макроопределения в скобки. Например:
#define MIN(a,b) (((a)<(b))?(a):(b))
Если макроопределение достаточно сложное, и требуется комментарий
к нему, то разумнее написать комментарий вида /* */, поскольку
в реализации С++ может использоваться препроцессор С, который не
распознает комментарии вида //. Например:
#define m2(a) something(a) /* глубокомысленный комментарий */
С помощью макросредств можно создать свой собственный язык,
правда, скорее всего, он будет непонятен другим. Кроме того, препроцессор
С предоставляет довольно слабые макросредства. Если ваша задача
нетривиальна, вы, скорее всего, обнаружите, что решить ее с помощью этих
средств либо невозможно, либо чрезвычайно трудно. В качестве
альтернативы традиционному использованию макросредств в язык введены
конструкции const, inline и шаблоны типов. Например:
const int answer = 42;
template<class T>
inline T min(T a, T b) { return (a<b)?a:b; }
1. (*1) Составьте следующие описания: функция с параметрами типа
указатель на символ и ссылка на целое, невозвращающая значения;
указатель на такую функцию; функция с параметром, имеющим тип
такого указателя; функция, возвращающая такой указатель. Напишите
определение функции, у которой параметр и возвращаемое значение
имеют тип такого указателя. Подсказка: используйте typedef.
2. (*1) Как понимать следующее описание? Где оно может пригодиться?
typedef int (rifii&) (int, int);
3. (*1.5) Напишите программу, подобную той, что выдает "Hello, world".
Она получает имя (name) как параметр командной строки и выдает
"Hello, name". Измените программу так, чтобы она получала
произвольное число имен и всем им выдавала свое приветствие:
"Hello, ...".
4. (1.5) Напишите программу, которая, беря из командной строки
произвольное число имен файлов, все эти файлы переписывает
один за другим в cout. Поскольку в программе происходит
конкатенация файлов, вы можете назвать ее cat от слова
concatenation - конкатенация).
5. (*2) Переведите небольшую программу с языка С на С++. Измените
заголовочные файлы так, чтобы они содержали описание всех
вызываемых функций и описание типов всех параметров. По возможности
все команды #define замените конструкциями enum, const или
inline. Удалите из файлов .c все описания внешних, а определения
функций приведите к виду, соответствующему С++. Вызовы malloc() и
free() замените операциями new и delete. Удалите ненужные операции
приведения.
6. (*2) Напишите функцию sort() ($$4.6.9), использующую более
эффективный алгоритм сортировки.
7. (*2) Посмотрите на определение структуры tnode в $$R.9.3. Напишите
функцию, заносящую новые слова в дерево узлов tnode. Напишите
функцию для вывода узлов дерева tnode. Напишите функцию,
которая производит такой вывод в алфавитном порядке.
Измените структуру tnode так, чтобы в ней содержался
только указатель на слово произвольной длины, которое размещается
с помощью new в свободной памяти. Измените функцию так, чтобы
она работала с новой структурой tnode.
8. (*1) Напишите функцию itoa(), которая использовалась в примере
из $$4.6.8.
9. (*2) Узнайте, какие стандартные заголовочные файлы есть в вашей
системе. Поройтесь в каталогах /usr/include или /usr/include/CC
(или в тех каталогах, где хранятся стандартные заголовочные
файлы вашей системы). Прочитайте любой показавшийся интересным
файл.
10. (*2) Напишите функцию, которая будет переворачивать двумерный
массив. (Первый элемент массива станет последним).
11. (*2) Напишите шифрующую программу, которая читает символы из
cin и пишет их в cout в зашифрованном виде. Можно использовать
следующий простой метод шифрации: для символа s зашифрованное
представление получается в результате операции s^key[i], где
key - массив символов, передаваемый в командной строке. Символы
из массива key используются в циклическом порядке, пока не будет
прочитан весь входной поток. Первоначальный текст получается
повторным применением той же операции с теми же элементами key.
Если массив key не задан (или задана пустая строка), шифрация не
происходит.
12. (*3) Напишите программу, которая помогает дешифрировать текст,
зашифрованный описанным выше способом, когда ключ (т.е. массив
key) неизвестен. Подсказка: см. D Kahn "The Codebreakers",
Macmillan, 1967, New York, стр. 207-213.
13. (*3) Напишите функцию обработки ошибок, первый параметр который
подобен форматирующей строке-параметру printf() и содержит форматы
%s, %c и %d. За ним может следовать произвольное количество
числовых параметров. Функцию printf() не используйте. Если смысл
формата %s и других форматов вам неизвестен, обратитесь к $$10.6.
Используйте <stdarg.h>.
14. (*1) Какое имя вы выбрали бы для типов указателей на функции,
которые определяются с помощью typedef?
15. (*2) Исследуйте разные программы, чтобы получить представление
о разных используемых на практике стилях именования. Как
используются заглавные буквы? Как используется подчерк? В каких
случаях используются такие имена, как i или x?
16. (*1) Какие ошибки содержатся в следующих макроопределениях?
#define PI = 3.141593;
#define MAX(a,b) a>b?a:b
#define fac(a) (a)*fac((a)-1)
17. (*3) Напишите макропроцессор с простыми возможностями, как у
препроцессора С. Текст читайте из cin, а результат записывайте
в cout. Вначале реализуйте макроопределения без параметров.
Подсказка: в программе калькулятора есть таблица имен и
синтаксический анализатор, которыми можно воспользоваться.
18. (*2) Напишите программу, извлекающую квадратный корень из двух (2)
с помощью стандартной функции sqrt(), но не включайте в программу
<math.h>. Сделайте это упражнение с помощью функции sqrt()
на Фортране.
19. (*2) Реализуйте функцию print() из $$4.6.7.
"Эти типы не абстрактные, они столь же реальны,
как int и float"
- Даг Макилрой
В этой главе описываются возможности определения новых типов,
для которых доступ к данным ограничен заданным множеством
функций, осуществляющих его. Объясняется, как можно использовать
члены структуры данных, как ее защищать, инициализировать и,
наконец, уничтожать. В примерах приведены простые классы для
управления таблицей имен, работы со стеком, множеством и
реализации дискриминирующего (т.е. надежного) объединения.
Следующие три главы завершают описание возможностей С++ для
построения новых типов, и в них содержится больше интересных
примеров.
Понятие класса, которому посвящена эта и три следующих главы, служит
в С++ для того, чтобы дать программисту инструмент построения новых
типов. Ими пользоваться не менее удобно, чем встроенными.
В идеале использование определенного пользователем типа не должно
отличаться от использования встроенных типов. Различия возможны только
в способе построения.
Тип есть вполне конкретное представление некоторого понятия.
Например, в С++ тип float с операциями +, -, * и т.д. является
хотя и ограниченным, но конкретным представлением математического
понятия вещественного числа. Новый тип создается для того, чтобы
стать специальным и конкретным представлением понятия, которое не находит
прямого и естественного отражения среди встроенных типов. Например,
в программе из области телефонной связи можно ввести тип
trunk_module (линия-связи), в видеоигре - тип explosion (взрыв),
а в программе, обрабатывающей текст, - тип list_of_paragraphs
(список-параграфов). Обычно проще понимать и изменять программу,
в которой типы хорошо представляют используемые в задаче понятия.
Удачно подобранное множество пользовательских типов делает программу
более ясной. Оно позволяет транслятору обнаруживать недопустимое
использование объектов, которое в противном случае останется
невыявленным до отладки программы.
Главное в определении нового типа - это отделить несущественные
детали реализации (например, расположение данных в объекте нового
типа) от тех его характеристик, которые существенны для правильного
его использования (например, полный список функций, имеющих доступ
к данным). Такое разделение обеспечивается тем, что вся работа со
структурой данных и внутрение, служебные операции над нею доступны
только через специальный интерфейс (через "одно горло").
Глава состоит из четырех частей:
$$5.2 Классы и члены. Здесь вводится основное понятие
пользовательского типа, называемого классом. Доступ к объектам
класса может ограничиваться множеством функций, описания
которых входят в описание класса. Эти функции называются
функциями-членами и друзьями. Для создания объектов класса
используются специальные функции-члены, называемые
конструкторами. Можно описать специальную функцию-член
для удаления объектов класса при его уничтожении. Такая
функция называется деструктором.
$$5.3 Интерфейсы и реализации. Здесь приводятся два примера
разработки, реализации и использования классов.
$$5.4 Дополнительные свойства классов. Здесь приводится много
дополнительных подробностей о классах. Показано, как
функции, не являющейся членом класса, предоставить доступ
к его частной части. Такую функцию называют другом класса.
Вводятся понятия статических членов класса и указателей
на члены класса. Здесь же показано, как определить
дискриминирующее объединение.
$$5.5 Конструкторы и деструкторы. Объект может создаваться как
автоматический, статический или как объект в свободной
памяти. Кроме того, объект может быть членом некоторого
агрегата (массива или другого класса), который тоже
можно размещать одним из этих трех способов. Подробно
объясняется использование конструкторов и деструкторов,
описывается применение определяемых пользователем функций
размещения в свободной памяти и функций освобождения памяти.
Класс - это пользовательский тип. Этот раздел знакомит с основными
средствами определения класса, создания его объектов, работы с
такими объектами и, наконец, удаления этих объектов после
использования.
Посмотрим, как можно представить в языке понятие даты, используя
для этого тип структуры и набор функций, работающих с переменными
этого типа:
struct date { int month, day, year; };
date today;
void set_date(date*, int, int, int);
void next_date(date*);
void print_date(const date*);
// ...
Никакой явной связи между функциями и структурой date нет. Ее можно
установить, если описать функции как члены структуры:
struct date {
int month, day, year;
void set(int, int, int);
void get(int*, int* int*);
void next();
void print();
};
Описанные таким образом функции называются функциями-членами. Их можно
вызывать только через переменные соответствующего типа, используя
стандартную запись обращения к члену структуры:
date today;
date my_birthday;
void f()
{
my_birthday.set(30,12,1950);
today.set(18,1,1991);
my_birthday.print();
today.next();
}
Поскольку разные структуры могут иметь функции-члены с одинаковыми
именами, при определении функции-члена нужно указывать имя структуры:
void date::next()
{
if (++day > 28 ) {
// здесь сложный вариант
}
}
В теле функции-члена имена членов можно использовать без указания
имени объекта. В таком случае имя относится к члену того объекта,
для которого была вызвана функция.
Мы определили несколько функций для работы со структурой date, но из ее
описания не следует, что это единственные функции, которые
предоставляют доступ к объектам типа date. Можно установить такое
ограничение, описав класс вместо структуры:
class date {
int month, day, year;
public:
void set(int, int, int);
void get(int*, int*, int*);
void next();
void print()
};
Служебное слово public (общий) разбивает описание класса на две части.
Имена, описанные в первой частной (private) части класса, могут
использоваться только в функциях-членах. Вторая - общая часть -
представляет собой интерфейс с объектами класса. Поэтому структура - это
такой класс, в котором по определению все члены являются общими.
Функции-члены класса определяются и используются точно так же, как
было показано в предыдущем разделе:
void date::print() // печать даты в принятом в США виде
{
cout << month << '/' << day << '/' << year ;
}
Однако от функций не членов частные члены класса date уже ограждены:
void backdate()
{
today.day--; // ошибка
}
Есть ряд преимуществ в том, что доступ к структуре данных ограничен
явно указанным списком функций. Любая ошибка в дате (например,
December, 36, 1985) могла быть внесена только функцией-членом,
поэтому первая стадия отладки - локализация ошибки - происходит
даже до первого пуска программы. Это только частный случай общего
правила: любое изменение в поведении типа date может и должно
вызываться изменениями в его членах. Другое преимущество в том, что
потенциальному пользователю класса для работы с ним достаточно
знать только определения функций-членов.
Защита частных данных основывается только на ограничении
использования имен членов класса. Поэтому ее можно обойти с
помощью манипуляций с адресами или явных преобразований типа,
но это уже можно считать мошенничеством.
В функции-члене можно непосредственно использовать имена членов
того объекта, для которого она была вызвана:
class X {
int m;
public:
int readm() { return m; }
};
void f(X aa, X bb)
{
int a = aa.readm();
int b = bb.readm();
// ...
}
При первом вызове readm() m обозначает aa.m, а при втором - bb.m.
У функции-члена есть дополнительный скрытый параметр, являющийся
указателем на объект, для которого вызывалась функция. Можно явно
использовать этот скрытый параметр под именем this. Считается, что
в каждой функции-члене класса X указатель this описан неявно как
X *const this;
и инициализируется, чтобы указывать на объект, для которого
функция-член вызывалась. Этот указатель нельзя изменять, поскольку
он постоянный (*const). Явно описать его тоже нельзя, т.к. this -
это служебное слово. Можно дать эквивалентное описание класса X:
class X {
int m;
public:
int readm() { return this->m; }
};
Для обращения к членам использовать this излишне. В основном this
используется в функциях-членах, непосредственно работающих с
указателями. Типичный пример - функция, которая вставляет элемент
в список с двойной связью:
class dlink {
dlink* pre; // указатель на предыдущий элемент
dlink* suc; // указатель на следующий элемент
public:
void append(dlink*);
// ...
};
void dlink::append(dlink* p)
{
p->suc = suc; // т.е. p->suc = this->suc
p->pre = this; // явное использование "this"
suc->pre = p; // т.е. this->suc->pre = p
suc = p; // т.е. this->suc = p
}
dlink* list_head;
void f(dlink* a, dlink* b)
{
// ...
list_head->append(a);
list_head->append(b);
}
Списки с такой общей структурой служат фундаментом списочных классов,
описываемых в главе 8. Чтобы присоединить звено к списку, нужно
изменить объекты, на которые настроены указатели this, pre и suc.
Все они имеют тип dlink, поэтому функция-член dlink::append() имеет
к ним доступ. Защищаемой единицей в С++ является класс, а не отдельный
объект класса.
Можно описать функцию-член таким образом, что объект, для которого
она вызывается, будет доступен ей только по чтению. Тот факт, что
функция не будет изменять объект, для которого она вызывается
(т.е. this*), обозначается служебным словом const в конце списка
параметров:
class X {
int m;
public:
readme() const { return m; }
writeme(int i) { m = i; }
};
Функцию-член со спецификацией const можно вызывать для постоянных
объектов, а функцию-член без такой спецификации - нельзя:
void f(X& mutable, const X& constant)
{
mutable.readme(); // нормально
mutable.writeme(7); // нормально
constant.readme(); // нормально
constant.writeme(7); // ошибка
}
В этом примере разумный транслятор смог бы обнаружить, что
функция X::writeme() пытается изменить постоянный объект. Однако,
это непростая задача для транслятора. Из-за раздельной
трансляции он в общем случае не может гарантировать "постоянство"
объекта, если нет соответствующего описания со спецификацией
const. Например, определения readme() и writeme() могли быть в
другом файле:
class X {
int m;
public:
readme() const;
writeme(int i);
};
В таком случае описание readme() со спецификацией const существенно.
Тип указателя this в постоянной функции-члене класса X есть
const X *const. Это значит, что без явного приведения с помощью this
нельзя изменить значение объекта:
class X {
int m;
public:
// ...
void implicit_cheat() const { m++; } // ошибка
void explicit_cheat() const { ((X*)this)->m++; }
// нормально
};
Отбросить спецификацию const можно потому, что понятие
"постоянства" объекта имеет два значения. Первое, называемое
"физическим постоянством" состоит в том, что объект хранится
в защищенной от записи памяти. Второе, называемое "логическим
постоянством" заключается в том, что объект выступает как
постоянный (неизменяемый) по отношению к пользователям. Операция
над логически постоянным объектом может изменить часть данных
объекта, если при этом не нарушается его постоянство
с точки зрения пользователя. Операциями, ненарушающими логическое
постоянство объекта, могут быть буферизация значений, ведение
статистики, изменение переменных-счетчиков в постоянных
функциях-членах.
Логического постоянства можно достигнуть приведением, удаляющим
спецификацию const:
class calculator1 {
int cache_val;
int cache_arg;
// ...
public:
int compute(int i) const;
// ...
};
int calculator1::compute(int i) const
{
if (i == cache_arg) return cache_val;
// нелучший способ
((calculator1*)this)->cache_arg = i;
((calculator1*)this)->cache_val = val;
return val;
}
Этого же результата можно достичь, используя указатель на данные
без const:
struct cache {
int val;
int arg;
};
class calculator2 {
cache* p;
// ...
public:
int compute(int i) const;
// ...
};
int calculator2::compute(int i) const
{
if (i == p->arg) return p->val;
// нелучший способ
p->arg = i;
p->val = val;
return val;
}
Отметим, что const нужно указывать как в описании, так и в определении
постоянной функции-члена. Физическое постоянство обеспечивается
помещением объекта в защищенную по записи память, только если в классе
нет конструктора ($$7.1.6).
Инициализация объектов класса с помощью таких функций как set_date()
- неэлегантное и чреватое ошибками решение. Поскольку явно не было
указано, что объект требует инициализации, программист может либо забыть
это сделать, либо сделать дважды, что может привести к столь же
катастрофическим последствиям. Лучше дать программисту возможность
описать функцию, явно предназначенную для инициализации объектов.
Поскольку такая функция конструирует значение данного типа, она
называется конструктором. Эту функцию легко распознать - она имеет
то же имя, что и ее класс:
class date {
// ...
date(int, int, int);
};
Если в классе есть конструктор, все объекты этого класса будут
проинициализированы. Если конструктору требуются параметры, их
надо указывать:
date today = date(23,6,1983);
date xmas(25,12,0); // краткая форма
date my_birthday; // неправильно, нужен инициализатор
Часто бывает удобно указать несколько способов инициализации
объекта. Для этого нужно описать несколько конструкторов:
class date {
int month, day, year;
public:
// ...
date(int, int, int); // день, месяц, год
date(int, int); // день, месяц и текущий год
date(int); // день и текущие год и месяц
date(); // стандартное значение: текущая дата
date(const char*); // дата в строковом представлении
};
Параметры конструкторов подчиняются тем же правилам о типах