10.4. Класс – тип данных, определенный программистом

При «эпизодическом» ООП разрабатываемые классы представляют собой «недостающие» типы данных. По своим свойствам они могут приближаться к базовым типам данным, вплоть до наличия общепринятой «арифметики значений» и переопределения стандартных операций присваивания, сравнения и ввода-вывода в текстовые потоки.

Классы стандартных потоков ввода-вывода

Переопределение операций в Си++ позволяет ввести единую интерпретацию операций по отношению ко всем базовым типам данных и разрабатываемым классам. Прежде всего, это нужно сделать по отношению к стандартному вводу-выводу. Не вдаваясь в подробности, проиллюстрируем, как это примерно реализовано в библиотеке iostream.

CPP

class istream {
  …

      istream&
      operator>>(int v) {
    csanf(“ % d”, &v);
    return *this;
  }

  istream& operator>>(float v) {
    scanf(“ % f”, &v);
    return *this;
  }

  istream& operator>>(char c) {
        … }

  istream& operator>>(char c[]) {
        … }

  void getline(char c[], int n) {}
};

class ostream {
  …

      ostream&
      operator<<(int v) {
    printf(“ % d”, &v);
    return *this;
  }

  ostream& operator<<(float v) {
    printf(“ % f”, &v);
    return *this;
  }

  ostream& operator<<(char c) {
        … }

  ostream& operator<<(char c[]) {
        … }
};

extern istream cin;

extern ostream cout;

В классах istream и ostream переопределены операции >> и << для всех базовых типов данных и массивов символов в виде конвейера ссылок. В самой же библиотеке имеются два объекта этих классов – cin и cout. Это позволяет записывать выражения вида

CPP

cout << a << b << “AAAAAA”;

cin >> a >> b;

операндами в которых могут быть переменные и выражения базовых типов, а также массивы символов (строки).

Чтобы стандартные потоки ввода-вывода «понимали» объекты разрабатываемых классов, необходимо переопределить операцию вида ostream << newclass и istream >> newclass. Это можно сделать только в виде дружественных операторов в пользовательском класса newclass.

CPP

class newclass {…

  friend operator ostream& <<(ostream &O, newclass &R){… O << R.vv… return O; }

  friend operator istream& <<(istream &O, newclass &R){… O >> R.vv… return O; }

}

Аналогичным образом определены классы файловых и строковых потоков fstream, ifstream, ofstream, istrstream, ostrstream, которые имеют в качестве источников и приемников данных текстовые файлы и массивы символов (строки). Естественно, что в них предусмотрены необходимые конструкторы и методы открытия и закрытия.

CPP

//----------------------------------------------------------------------------------102-00.cpp

void main() {
  istrstream I("2 3.4 abcd");  // Поток с источником – текстовой строкой

  int a;
  double b;
  char c, s[10], out[80];

  I >> a >> b >> c >> s;  // Чтение из потока - строки

  ostrstream O(out, 80);  // Поток с приемником – текстовой строкой

  O << b << " " << c << "\n" << a << " " << s << '\0';

  cout << out << endl;  // Вывод строки в стандартный поток

  ifstream F1("104-00.cpp");  // Поток с источником – файлом (имя в конструкторе)

  ofstream F2;  // Поток с приемником - файлом

  F2.open("104-00.txt");  // Отдельный метод открытия файла

  if (!F1.good() || !F2.good())
    return;

  while (!F1.eof()) {  // Построчное переписывание файла

    F1.getline(out, 80);

    F2 << out << endl;
  }

  F1.close();
  F2.close();
}

Тип данных – текстовая строка

Все «нормальные» языки программирования работают со строками как с базовым типом данным, встроенным в язык. В Си++ легко определить класс, реализующий «джентльменский набор» операций со строками с использованием и в духе стандартных арифметических операций. В объекте текстовая строка хранится в динамическом массиве str. Внутренние закрытые методы класса реализуют наиболее часто используемые классом функции, их внешнее использование не всегда может быть корректным.

CPP

//-----------------------------------------------------------104-01.cpp
class string {
  char* str;

  void load(char* s) { str = strdup(s); }

  void add(char* s) {  // Объединение со строкой

    str = (char*)realloc(str, strlen(str) + strlen(s) + 1);

    strcat(str, s);
  }

  int find(char* s) {  // Поиск подстроки

    for (int k = 0; str[k] != 0; k++) {
      for (int i = 0; s[i] != 0 && s[i] == str[k + i]; i++)
        ;

      if (s[i] == 0)
        return i;
    }

    return -1;
  }  // Сравнение строк

  int cmp(string& t) { return strcmp(str, t.str); }

 public:
  string() { load(""); }

  string(char* s) { load(s); }

  string(string& t) { load(t.str); }

  ~string() { delete[] str; }

Операция сложения (конкатенации) строк переопределена для различных сочетаний типов операндов в виде «конвейера значений» и сохраняет неизменным значения операндов.

CPP

//-----------------------------------------------------------104-01.cpp

string& operator=(string& r) {
  delete[] str;
  load(r.str);
  return *this;
}

string operator+(char* c) {
  string t(str);
  t.add(c);
  return t;
}

string operator+(string& r) {
  string t(str);
  t.add(r.str);
  return t;
}

friend string operator+(char* s, string& t)

{
  string x(s);
  x.add(t.str);
  return x;
}

int operator==(string& t) {
  return cmp(t) == 0;
}

int operator!=(string& t) {
  return cmp(t) != 0;
}

int operator<(string& t) {
  return cmp(t) < 0;
}

int operator<=(string& t) {
  return cmp(t) <= 0;
}

int operator>(string& t) {
  return cmp(t) > 0;
}

int operator>=(string& t) {
  return cmp(t) >= 0;
}

Операция [] переопределена для целого индекса как извлечение из строки символа с заданным номером. Если операнд в скобках является строкой (массивом символов или объектом string), то операция выполняет поиск вхождения строки и текущем объекте. Операция () переопределена как извлечение фрагмента по заданным индексам. Она создает локальный объект – копию фрагмента и возвращает его по значению.

CPP

//-----------------------------------------------------------104-01.cpp

char operator[](int k) {
  if (k < 0 || k >= strlen(str))
    return '?';

  return str[k];
}

int operator[](char* c) {
  return find(c);
}

int operator[](string& t) {
  return find(t.str);
}

string operator()(int n1, int n2 = -1) {  // по умолчанию второй = -1

  if (n2 == -1)
    n2 = strlen(str);  // один операнд – до конца строки

  if (n1 < 0 || n2 < 0 || n1 > strlen(str) || n2 > strlen(str) || n1 > n2)

  {
    return string("");
  }  // выход за границу – пустая строка

  char c = str[n2];
  str[n2] = 0;  // «ограничить» строку по концу фрагмента

  string x(str + n1);  // создать строку – копию, начиная с n1

  str[n2] = c;
  return x;
}  // восстановить текущий, вернуть копию

//-----------------------------------------------------------104-01.cpp

friend ostream& operator<<(ostream& IO, string& t) {
  IO << t.str << endl;
  return IO;
}

friend istream& operator>>(istream& IO, string& t) {
  char c[1000];

  IO.getline(c, 1000);
  delete[] t.str;
  t.str = strdup(c);

  return IO;
}

Тип данных – матрица произвольной размерности

Внутреннее представление матрицы произвольной размерности – динамический массив указателей на строки, доступный через «двойной» указатель pd. Методы создания копии и разрушения структуры данных закрыты, поскольку их вызов извне не всегда может быть корректен.

CPP

//------------------------------------------------------104-02.cpp

//------- Матрица с динамическим массивом указателей на строки

class matrix {
  int n, m;  // Размерности матрицы y,x

  double** pd;  // Указатель на ДМУ на строки

  //----- Закрытые методы создания копии ДМУ и разрушения

  void load(int n0, int m0, double** d = NULL) {
    n = n0;
    m = m0;

    pd = new double*[n];

    for (int i = 0; i < n; i++) {
      pd[i] = new double[m];

      for (int j = 0; j < m; j++)

        pd[i][j] = (d == NULL ? 0 : d[i][j]);
    }
  }

  void destroy() {
    for (int i = 0; i < n; i++)

      delete[] pd[i];

    delete[] pd;
  }

Многообразие конструкторов обеспечивает различные способы заполнения матрицы, конструктор копирования – передачу объекта по значению. Это необходимо для переопределения арифметических операций в виде «конвейера значений». Аналогично, требуется переопределение операции присваивания с учетом корректного копирования внешних динамических данных.

CPP

//------------------------------------------------------104-02.cpp

//---- Конструктор пустой матрицы

matrix(int y, int x) {
  load(y, x);
}

//---- Конструктор, заполняющий матрицу из линейного массива

matrix(int y, int x, double* q) {
  load(y, x);

  for (int i = 0; i < n; i++) {  // Заполнить строки матрицы

    for (int j = 0; j < m; j++)
      pd[i][j] = *q++;
  }
}

//---- Конструктор, заполняющий матрицу из списка коэффициентов

matrix(int y, int x, double a, ...) {
  double* q = &a;  // Указатель на список параметров функции

  load(y, x);

  for (int i = 0; i < n; i++) {  // Заполнить строки матрицы

    for (int j = 0; j < m; j++)
      pd[i][j] = *q++;
  }
}

//---- Конструктор, заполняющий матрицу из списка коэффициентов

// Формат : int,int,double координаты и значение коэффициента

matrix(int y, int x, int a, ...) {
  int* q = &a;  // Указатель на список параметров функции

  load(y, x);

  while (*q >= 0) {  // Ограничитель списка значение <0

    int yy = *q++;  // Извлечь координаты и коэффициент

    int xx = *q++;

    double vv = *((double*)q);
    q += sizeof(double) / sizeof(int);

    if (xx >= 0 && xx < m && yy >= 0 && yy < n)
      pd[yy][xx] = vv;
  }
}

//---- Конструктор копирования

matrix(matrix& R) {
  load(R.n, R.m, R.pd);
}

//---- Деструктор

matrix::~matrix() {
  destroy();
}

//----- Переопределение операции присваивания

matrix& operator=(matrix& T) {
  destroy();

  load(T.n, T.m, T.pd);

  return *this;
}

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

CPP

//---- Возвращает ссылку на заданный коэффициент

double& operator()(int yy, int xx) {
  static double ERROR = 0;

  if (xx >= 0 && xx < m && yy >= 0 && yy < n)
    return pd[yy][xx];

  else
    return ERROR;
}

В арифметических операциях одной из проблем является изменение размерности матриц. Если это делать на уровне внутреннего представления данных, то получим достаточно громоздкий код. Удобнее создавать дополнительные объекты требуемой размерности и возвращать их по значению.

CPP

//----- Переопределение операции сложения

matrix operator+(matrix& T) {
  int i, j;

  int nn = (n > T.n ? n : T.n);  // Определение максимальных размерностей

  int mm = (m > T.m ? m : T.m);

  matrix X(nn, mm);  // Создание внутреннего объекта

  for (i = 0; i < n; i++)

    for (j = 0; j < m; j++)
      X.pd[i][j] = pd[i][j];  // Копирование значений первого операнда

  for (i = 0; i < T.n; i++)  // Сложение со значениями второго операнда

    for (j = 0; j < T.m; j++)
      X.pd[i][j] = T.pd[i][j];

  return X; // Возврат результата по значению
};

Тип данных – разреженная матрица

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

при извлечении $A_{ij}$ производится поиск в массиве и возврат значения с такими координатами, при его отсутствии возвращается 0;
при записи $A_{ij}$ производится поиск в массиве значения с такими координатами. Если коэффициент найден, то происходит его обновление, если нет, то в массив добавляется новый коэффициент. Отдельного обсуждения требует запись нулевых коэффициентов. Это должно приводить не к обновлению найденной записи в массиве, а к ее удалению, иначе будет происходит «замусоривание» внутреннего массива нулевыми коэффициентами.

CPP

//----------------------------------------------------104-03.cpp

// Класс разреженной матрицы

class matrix {
  struct koeff {
    int x, y;  // "координаты" коэффициента

    double vv;  // значение коэффициента

  } * pd;  // динамический массив коэффициентов

  int nk, sz;  // текущая и полная размерности массива

  int N, M;  // размерности матрицы

  void extend() {  // перераспределение памяти

    if (nk != sz)
      return;

    sz *= 2;
    pd = (koeff*)realloc(pd, sz * sizeof(koeff));
  }

 public:
  matrix(int n0, int m0) {  // Конструктор

    N = n0;
    M = m0;
    nk = 0;
    sz = 10;

    pd = new koeff[sz];
  }

  double get(int yy, int xx) {  // Поиск коэффициента по координатам

    for (int i = 0; i < nk; i++)

      if (yy == pd[i].y && xx == pd[i].x)

        return pd[i].vv;

    return 0;
  }  // Добавление коэффициента по координатам

  void set(int yy, int xx, double v) {
    for (int i = 0; i < nk; i++)

      if (yy == pd[i].y && xx == pd[i].x) {
        if (v != 0)

          pd[i].vv = v;  // Коэффициент найден - обновить

        else {  // Запись нулевого - удалить

          for (int j = i; j < nk - 1; j++)
            pd[j] = pd[j + 1];

          nk--;
        }

        return;
      }

    if (v == 0)
      return;  // Не найден и равен 0 - выйти

    pd[nk].x = xx;
    pd[nk].y = yy;  // Не найден и не равен 0 - ,добавить

    pd[nk].vv = v;

    nk++;
    extend();
  }

Внутреннее и внешнее представление данных в классе создает различные «системы координат», в которых операции могут быть реализованы с разной эффективностью. Например, если делать сложение матриц во «внешней» системе координат, т.е. используя двойной цикл извлечения элементов Aij, то львиную долю времени будет занимать абсолютно бесполезное сложение нулевых коэффициентов. Очевидно, эффективнее использовать внутреннее представление. Просматривать массив коэффициентов второй матрицы (в «системе координат» внутреннего представления) и выполнять их сложение с первой (во внешнем представлении).

CPP

//----------------------------------------------------104-03.cpp

void add(matrix& T) {  // Сложение (второй объект с текущим)

  for (int i = 0; i < T.nk;
       i++) {  // Перебор ненулевых коэффициентов второй матрицы

    int ii = T.pd[i].y;

    int jj = T.pd[i].x;  // Сложение с "одноименным" коэффициентом первой

    set(ii, jj, get(ii, jj) + T.pd[i].vv);
  }
}

Тип данных – неориентированный граф

Неориентированный граф (см. 8.6), при его использовании в практических задачах часто вырождается в разреженную матрицу. Например, в транспортной сети, содержащей сотни узлов, каждый узел обычно связан с 2-3 соседями. В алгоритмах на графах часто используется перебор вершин, смежных с заданной. Поэтому внутреннее представление графа лучше всего выбрать таким образом, чтобы каждой вершине соответствовал собственный список ребер, например, в виде массива указателей на списки, содержащие номера смежных вершин и веса ребер.

CPP

//--------------------------------------------------------104-04.cpp

// Класс неориентированного графа, представленного массивом

// заголовков списков смежных вершин

class graph {
  struct link {  // Элемент списка смежных вершин

    int v2, lnt;  // Номер вершины и вес ребра

    link* next;

    link(int vv, int ll) {
      v2 = vv;
      lnt = ll;
      next = NULL;
    }
  };

  int n;  // размерность графа

  link** M;  // динамический массив указателей на списки

 public:
  operator int() { return n; }

  graph(int n0) {  // конструктор пустого графа

    n = n0;

    M = new link*[n];

    for (int i = 0; i < n; i++)
      M[i] = NULL;
  }

  void add(int k1, int k2, int v) {
    link* q = new link(k1, v);  // добавление ребра

    q->next = M[k2];
    M[k2] = q;  // добавление в список первой вершины

    q = new link(k2, v);  // добавление в список второй вершины

    q->next = M[k1];
    M[k1] = q;
  }

  // Конструктор из матрицы (массив указателей на строки)

  graph(int* pp[], int n0) {
    int i, j;

    n = n0;
    M = new link*[n];

    for (i = 0; i < n; i++)
      M[i] = NULL;

    for (i = 0; i < n; i++)  // Создать ребра только

      for (j = 0; j < i; j++)  // для ненулевых значений матрицы

        if (pp[i][j] != 0)
          add(i, j, pp[i][j]);
  }

В технологии ООП используется термин итератор, обозначающий внешний независимый «движок» для перемещения по структуре данных, размещенной внутри класса. Реализуется он в виде отдельного объекта, и применительно к графу будет содержать указатель на текущий элемент списка ребер выбранной вершины.

CPP

//--------------------------------------------------------104-04.cpp

// Итератор для списка смежных вершин (в классе graph)

struct iterator {
  link* cur;  // указатель на элемент списка

  iterator(link* p0) { cur = p0; }

  int next(int& v2, int& lnt2) {  // Возвращает значение текущего

    if (cur == NULL)
      return 0;  // и переходит к следующему элементу списка

    v2 = cur->v2;
    lnt2 = cur->lnt;

    cur = cur->next;

    return 1;
  }
};

// Метод, создающий итератор для заданной вершины

iterator first(int k) {
  return iterator(M[k]);
}

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

CPP

//--------------------------------------------------------104-04.cpp

void scan() {  // полный рекурсивный обход графа

  D = new int[n];  // массив отметок обхода вершин

  for (int i = 0; i < n; i++)
    D[i] = 0;

  scan_v(0);

  delete[] D;
}

private:  // рекурсивный метод обхода вершины
void scan_v(int i) {
  D[i] = 1;  // отметить вершину

  int v2, l2;

  graph::iterator II = first(i);

  while (II.next(v2, l2))  // Цикл просмотра соседей для текущей вершины

    if (D[v2] == 0)
      scan_v(v2);  // просмотр списка ребер

  D[i] = 0;
}                                         // если не отмечена - рекурсивный вызов

Алгоритмы, работающие с графом, могут быть встроены в класс в качестве методов, или же оставаться «классическими» функциями, использующими объекты класса графа и его итераторы.

CPP

//--------------------------------------------------------104-04.cpp

// Алгоритм Дейкстры, использующий классическую нотацию

graph GG(10);

GG.load("86-011.txt");  // Алгоритм Дейкстры

int i, j, k, N = GG;  // для поиска кратчайших путей

int* P = new int[N];

int* D = new int[N];

for (i = 0; i < N; i++)
  P[i] = 0, D[i] = 100000;

D[0] = 0;

while (1) {
  for (k = -1, i = 0; i < N; i++) {
    if (P[i] == 1)
      continue;  // В облаке

    if (k == -1 || D[i] < D[k])

      k = i;  // Ближайшая вне облака
  }

  if (k == -1)
    break;

  P[k] = 1;  // Внести текущую в облако

  int v2, l2;

  graph::iterator II =
      GG.first(k);  // Цикл просмотра соседей для текущей вершины

  while (II.next(v2, l2)) {  // с использованием итератора

    if (D[k] + l2 < D[v2])  // - если расстояние уменьшается

      D[v2] = D[k] + l2;
  }

Star

Edit on GitHub

10.3. Переопределение операций

10.5. Шаблоны. Классы структур данных