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:
void print_in_order(intset* set) (* int var; set-»iterate(var); while (set-»ok(var)) cout «„ set-“next(var) „« « “; *)
Другой способ задать итератор приводится в #6.8.
5.4 Друзья и Объединения
В это разделе описываются еще некоторые особенности, ксающиеся классов. Показано, как предоставить функции не члену доступ к закрытым членам. Описывается, как разрешать конфлиты имен членов, как можно делать вложенные описания классов, и как избежать нежелательной вложенности. Обсуждается также, как объекты класса могут совместно использовать члены данные, и как использовать указатели на члены. Наконец, приводится пример, показывающий, как построить дискриминирующее (экононое) объединение.
5.4.1 Друзья
Предположим, вы определили два класса, vector и matrix (вектор и матрица). Каждый скрывает свое представление и прдоставляет полный набор действий для манипуляции объектами его типа. Теперь определим функцию, умножающую матрицу на вектор. Для простоты допустим, что в векторе четыре элемента, которые индексируются 0...3, и что матрица состоит из четырех векторов, индексированных 0...3. Допустим также, что доступ к элементам вектора осуществляется через функцию elem(), котрая осуществляет проверку индекса, и что в matrix имеется аналогичная функция. Один подход состоит в определении глбальной функции multiply() (перемножить) примерно следующим образом:
vector multiply(matrix amp; m, vector amp; v); (* vector r; for (int i = 0; i«3; i++) (* // r[i] = m[i] * v; r.elem(i) = 0; for (int j = 0; j«3; j++) r.elem(i) += m.elem(i,j) * v.elem(j); *) return r; *)
Это своего рода «естественный» способ, но он очень неэфективен. При каждом обращении к multiply() elem() будет взываться 4*(1+4*3) раза.
Теперь, если мы сделаем multiply() членом класса vector, мы сможем обойтись без проверки индексов при обращении к элменту вектора, а если мы сделаем multiply() членом класса matrix, то мы сможем обойтись без проверки индексов при обрщении к элементу матрицы. Однако членом двух классов функция быть не может. Нам нужно средство языка, предоставляющее функции право доступа к закрытой части класса. Функция не член, получившая право доступа к закрытой части класса, назвается другом класса (friend). Функция становится другом класса после описания как friend. Например:
class matrix;
class vector (* float v[4]; // ... friend vector multiply(matrix amp;, vector amp;); *);
class matrix (* vector v[4]; // ... friend vector multiply(matrix amp;, vector amp;); *);
Функция друг не имеет никаких особенностей, помимо права доступа к закрытой части класса. В частности, friend функция не имеет указателя this (если только она не является полноравным членом функцией). Описание friend – настоящее описние. Оно вводит имя функции в самой внешней области видимости программы и сопоставляется с другими описаниями этого имени. Описание друга может располагаться или в закрытой, или в отрытой части описания класса. Где именно, значения не имеет.
Теперь можно написать функцию умножения, которая исползует элементы векторов и матрицы непосредственно:
vector multiply(matrix amp; m, vector amp; v); (* vector r; for (int i = 0; i«3; i++) (* // r[i] = m[i] * v; r.v[i] = 0;
for (int j = 0; j«3; j++) r.v[i] += m.v[i][j] * v.v[j]; *) return r; *)
Есть способы преодолеть эту конкретную проблему эффетивности не используя аппарат friend (можно было бы определить операцию векторного умножения и определить multiply() с ее помощью). Однако существует много задач, кторые проще всего решаются, если есть возможность предоствить доступ к закрытой части класса функции, которая не явлется членом этого класса. В Главе 6 есть много примеров применения friend. Достоинства функций друзей и членов будут обсуждаться позже.
Функция член одного класса может быть другом другого. Например:
class x (* // ... void f(); *);
class y (* // ... friend void x::f(); *);
Нет ничего необычного в том, что все функции члены однго класса являются друзьями другого. Для этого есть даже блее краткая запись:
class x (* friend class y; // ... *);
Такое описание friend делает все функции члены класса y друзьями x.
5.4.2 Уточнение* Имени Члена
– * Иногда называется также квалификацией. (прим. перев.)
Иногда полезно делать явное различие между именами члнов класса и прочими именами. Для этого используется операция ::, «разрешения области видимости»:
class x (* int m; public: int readm() (* return x::m; *) void setm(int m) (* x::m = m; *) *);
В x::setm() имя параметра m прячет член m, поэтому единственный способ сослаться на член – это использовать его уточненное имя x::m. Операнд в левой части :: должен быть именем класса.
Имя с префиксом :: (просто) должно быть глобальным имнем. Это особенно полезно для того, чтобы можно было исползовать часто употребимые имена вроде read, put и open как имена функций членов, не теряя при этом возможности обращатся к той версии функции, которая не является членом. Например:
class my_file (* // ... public: int open(char*, char*); *);
int my_file::open(char* name, char* spec) (* // ... if (::open(name,flag))(*//использовать open() из UNIX (2) // ... *) // ... *)
5.4.3 Вложенные Классы
Описание класса может быть вложенным. Например:
class set (* struct setmem (* int mem; setmem* next; setmem(int m, setmem* n) (* mem=m; next=n; *) *); setmem* first; public: set() (* first=0; *) insert(int m) (* first = new setmem(m,first);*) // ... *);
Если только вложенный класс не является очень простым, в таком описании трудно разобраться. Кроме того, вложение класов – это не более чем соглашение о записи, поскольку вложеный класс не является скрытым в области видимости лексически охватывающего класса:
class set (* struct setmem (* int mem; setmem* next; setmem(int m, setmem* n) *); // ... *);
setmem::setmem(int m, setmem* n) (* mem=m, next=n*)
setmem m1(1,0); Такая запись, как set::setmem::setmem(), не является ни необходимой, ни допустимой.
