C++
Шрифт:
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) „« «\n“; *)
Другой способ задать итератор приводится в #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 как имена функций членов, не теряя при этом возможности обращатся к той версии функции, которая не является членом. Например: