#include "classarray.h" using namespace std; class Student: public Person{ private: string univ; // Университет
Array marks; // Оценки public:
Student() : marks(3), univ("МГУ") { }
Student(const string& name, int age, const string& u, int m):
Person(name, age), univ(u), marks(m) { } void setMark(int i, int mark) { if (i < 0 || i >= marks.length()) throw - 1; marks[i] = mark;
} friend ostream & operator<< (ostream & os, const Student &s){ os<<(Person)s; os << s.univ << endl; for (int i = 0; i < s.marks.length(); ++i) os << s.marks[i] << " "; os << endl; return os;
}
};
83
Поскольку теперь для хранения оценок используется объект marks класса Array, он берёт на себя всю работу с динамической памятью. Бла- годаря этому код класса Student становится проще. Это отражено на
UML диаграмме (рис.2.3).
Рис.2.3. UML диаграмма к примеру 9
Теперь класс Student не нуждается в переопределении конструкто- ра копии, деструктора и операции присваивания. Работают их версии по умолчанию, в которых происходит вызов соответствующих функций клас- сов Array и Person.
Например, конструктор копии, создаваемый по умолчанию, выглядит следующим образом:
Student(const Student& s):
Person(s),univ(s.univ),marks(s.marks){ }
84
Поэтому создавать собственную реализацию нет никакого смысла.
Она ничем не будет отличаться от версии по умолчанию.
Старайтесь все динамически выделяемые ресурсы оборачивать в от- дельные классы.
Если использовать класс Array из примера 4, то возникают ошибки компиляции в операции вывода в поток. Это связано с тем, что для кон- стантного объекта s класса Student используется неконстантные функ- ция для операции индексации класса Array. friend ostream & operator<< (ostream & os, const Student & s) { os<<(Person)s; os << s.univ << endl; for (int i = 0; i < s.marks.length(); ++i) os << s.marks[i] << " "; os << endl; return os;
}
Данная проблема описывалась при обсуждении примера 4, для её ре- шения предлагалось добавить реализацию константной операции индекси- рования. Следующий фрагмент кода демонстрирует описанные изменения. class Array {
… public:
… int& operator [] (int i); int operator [] (int i) const;
…
}; int& Array::operator [] (int i) { return A[i];
} int Array::operator [] (int i) const { return A[i];
}
85
Если в классе предполагается использование операции индексирования, то рекомендуется всегда реализовывать двумя способами.
В случае разработки сложных классов, использующих механизмы на- следования и включения объектов других классов, необходимо хорошо по- нимать порядок вызова конструкторов и деструкторов. Для конструкторов он выглядит следующим образом:
1. вызов конструктора базового класса;
2. вызов конструкторов для полей включённых объектов;
3. вызов конструктора основного объекта.
Деструкторы вызываются в обратном порядке:
1. вызов деструктора основного объекта;
2. вызов деструкторов полей;
3. вызов деструктора предка.
Порядок вызовов конструкторов для полей включённых объектов за- висит от порядка их следования в объявлении класса и не зависит от по- рядка в списке инициализаторов.
2.4.
Позднее связывание и виртуальные функции
Если базовый класс имеет несколько классов-наследников, то един- ственным способом объединить в одной коллекции объекты различных на- следников базового класса является создание массива (или другого контей- нера), содержащего указатели (или ссылки) на объекты базового класса.
Предположим, что у нас кроме класса Student есть ещё один на- следник класса Person – класс Professor. Создадим массив указателей на объекты класса Person.
Person *p [5];
86
Инициализируем массив p указателями на объекты классов наслед- ников. p[0] = new Student("Петров", 19, "МГУ", 3); p[1] = new Student("Кораблина", 18, "ЮФУ", 3); p[2] = new Professor ("Тьюринг", 32, "ИВЭ"); p[3] = new Professor ("Страуструп", 32, "ПМП"); p[4] = new Student("Гончаров", 20, " ЮФУ ", 3);
Предположим, в классе Person есть функция showInform, которая переопределена в классах-наследниках Student и Professor. При этом в случае следующего кода: for ( int i=0; i<5; ++i) p[i]->showInform(); мы увидим результат выполнения функции showInform, определённой в классе Person. Это обусловлено тем, что определение, какую из переоп- ределённых функций вызвать, происходит в момент компиляции по типу переменной-объекта или переменной-ссылки (указателя).
Определение на этапе компиляции вызываемого варианта переопреде- лённой функции называется
статическим, или
ранним, связыванием.
Однако в классах Student и Professor функция showInform переопределена и хотелось бы при вызове p[0]->showInform() увидеть информацию о студенте
Петрове, а при вызове p[2]->showInform() – о профессоре Тьюринге.
Для того чтобы обеспечить возможность определения, какая из пере- определённых функций должна быть вызвана, не на основе типа перемен- ной-ссылки или указателя, а на основе типа объекта, на
который они ссы- лаются, нужен другой механизм –
динамическое, или
позднее, связывание.
Определение на этапе выполнения вызываемого варианта переопреде- лённой функции называется динамическим
, или поздним, связыванием.
87
Позднее связывание реализует принцип полиморфизма. Полимор- физм позволяет выбирать вариант вызываемой функции в ходе выполнения программы.
Позднее связывание реализуется с помощью виртуальных функций.
Для того чтобы сделать функцию виртуальной, нужно перед её объ- явлением в базовом классе указать спецификатор virtual.
Например, объявление класса Person должно быть изменено сле- дующим образом: class Person{ public:
//все, как было описано выше, кроме функции showInform virtual void showInform(); private:
//все, как было описано выше
};
Реализация функции showInform как для класса Person, так и для классов-наследников остаётся без изменений.
Если объявление функции в базовом классе начинается с ключевого слова virtual, то это делает функцию виртуальной для базового класса и всех классов, производных от базового класса, — «виртуальная функция всегда виртуальна».
Поэтому добавлять спецификатор virtual в объявление функции showInform для классов-наследников не обязательно, но его использова- ние улучшает читаемость программы.
Рекомендуется всегда использовать спецификатор virtual в объявле- нии виртуальных функций, независимо от их расположения в иерархии на- следования.
88
Пример 12. Создать базовый класс shape, для хранения параметров произвольной геометрической фигуры на плоскости и вычисления её пло- щади по этим параметрам. Создать два класса-потомка rectangle (пара- метры: две стороны) и triangle (параметры: сторона и высота к ней), представляющие, соответственно, прямоугольник и треугольник.
#include using namespace std; class shape { protected: double x,y; public:
//конструкторы не создаём, так как
//используется автоматический конструктор по умолчанию void set_param(double x0, double y0) { x=x0; y=y0;
} virtual void show_area(){ cout<<"Area calculation for this class is undefined"; cout < }
}; class triangle: public shape { public:
//используется автоматический конструктор по умолчанию
//вызывающий конструктор по умолчанию базового класса void show_area() { cout< }
}; class rectangle : public shape { public:
//используется автоматический конструктор по умолчанию
//вызывающий конструктор по умолчанию базового класса void show_area() { cout< }
};
89 void tellMeAboutYourself(shape *s) { s-> show_area();
} int main() { shape *p[2]; triangle t; rectangle r; p[0]=&t; p[0]->set_param(10.0,5.0); p[0]->show_area(); p[1]=&r; p[1]->set_ param (10.0,5.0); p[1]->show_area(); for (auto x: p) tellMeAboutYourself(x); return 0;
}
В этом примере наследование не имеет целью расширение базового класса (рис. 2.4). Каждый из классов-наследников реализует свое собствен- ное поведение на основе виртуальной функции, объявленной в базовом классе.
Функция tellMeAboutYourself ожидает от любого наследника класса shape собственную реализацию функции show_area. Принято говорить, что между функцией tellMeAboutYourself и наследниками класса shape устанавливается соглашение по возможностям взаимодейст- вия. Такое соглашение называется интерфейсом.
В C++11 добавили новый тип цикла — foreach, который предоставля- ет более простой и безопасный способ итерации по массиву или любой другой структуре типа списка. Синтаксис цикла foreach для случая массива: for (переменная: массив) statement;
Выполняется итерация по каждому элементу массива, присваивая значение текущего элемента массива переменной. В целях лучшей произ-
90 водительности объявляемый элемент должен быть того же типа, что и эле- менты массива, иначе произойдёт неявное преобразование типа. Чтобы не задумываться о типах, в заголовке цикла for (auto x: p)используется автоматическое определение типа.
Рис.2.4. UML диаграмма классов примера 10
Для пользовательских типов данных, используемых в качестве парамет- ра цикла, рекомендуется применять auto.
До C++ 11 ключевое слово auto использовалось для явного указа- ния, что переменная имеет автоматический класс памяти (время существо- вания ограничено блоком, в котором она определена). Однако, поскольку все переменные в современном C++ по умолчанию имеют автоматический класс памяти, ключевое слово auto стало излишним и, следовательно, ус- таревшим.
91
Начиная с C++ 11, ключевое слово auto при инициализации пере- менной может использоваться вместо типа переменной,
чтобы сообщить компилятору, что он должен определить тип переменной исходя из ини- циализируемого значения. Это называется
выводом типа (или
автомати-ческим определением типов).
2.5. Абстрактные классы Во многих случаях вообще нет смысла давать определение виртуаль- ной функции в базовом классе. Например, в классе shape определение функции show_area() — лишь способ корректно сообщить об ошибке использования. Объект класса shape без конкретизации типа фигуры не может иметь площади. Для того чтобы не прибегать к такому искусствен- ному приёму, имеется возможность определять виртуальную функцию без реализации.
Виртуальная функция без реализации называется
чисто виртуальной.
Синтаксис объявления чисто виртуальной функции: virtual <тип> <имя> (<список параметров>) = 0;
Если класс имеет хотя бы одну чисто виртуальную функцию, его назы- вают
абстрактным классом.
Для абстрактного класса не могут быть созданы объекты. Такой класс может служить только в качестве базового в системе наследования и для создания указателей и ссылок, которые будут использованы при реализа- ции полиморфизма.
Если в базовом классе имеется чисто виртуальная функция, произ- водный класс должен иметь определение ее собственной реализации. Если
92 реализация хотя бы одной из чисто виртуальных функций не будет выпол- нена, производный класс, в свою очередь, останется абстрактным.
Абстрактные классы посредством чисто виртуальных функций опи- сывают интерфейс, который можно использовать в других классах или функциях, ожидая, что наследники реализуют эти функции.
Рассмотрим еще одну иерархию наследования для геометрических фигур на плоскости, на базе абстрактного класса shape.
Пример 13. Создать абстрактный класс shapeC и его наследников: классы circle и filled_circle.
#include
#include using namespace std; class shapeС { public:
//используется автоматический конструктор по умолчанию virtual shapeС() {} virtual double square() const =0; virtual shapeС* clone() const =0; virtual void debug(ostream &out) const=0;
}; class circle: public shapeС { public: circle(double r=0): radius(r) { }
circle() {} double square() const { return 3.14*radius*radius;
} circle* clone() const { return new circle(radius);
} void debug (ostream & out) const { out<<" radius = "< } protected: double radius;
}; class filled_circle: public circle { public: filled_circle (double r, int c): circle(r), color(c) { }
93
filled_circle() {} filled_circle* clone() const { return new filled_circle(radius, color);
} void debug (ostream & out) const { circle::debug(out); out<<" color = "< } private: int color;
}; int main() { shapeС *p[4]; circle t(5); filled_circle r(10, 255); p[0] = &t; p[1] = &r; p[2] = p[0]->clone(); p[3] = p[1]->clone(); for (auto x : p) { x->debug(cout);
} return 0;
}
Соответствующая UML диаграмма представлена на рисунке 2.5.
Массив p указателей на shapeС, представляет собой полиморфный контейнер, поскольку он может содержать указатели на circle и filled_circle.
Имея объекты наследников класса shapeС, можно их адреса присво- ить элементам массива p. circle t(5); filled_circle r(10, 255) p[0] = &t; p[1] = &r;
Но если потребуется создать копии этих двух элементов, операция присваивания не поможет, поскольку будет выполнено присваивание адре- сов. p[2] = p[0]; p[3] = p[1];
94
В этом случае p[2] и p[0] будут ссылаться на один и тот же объект t
, а p[3] и p[1] — на объект r.
Рис. 2.5. UML диаграмма классов к примеру 11
Решением данной проблемы могло бы быть создание виртуального конструктора, но конструкторы в C++ не могут быть виртуальными. По- этому для решения этой проблемы следует использовать функцию clone(). virtual shapeС* clone() const =0; class circle: public shapeС { public:
95 circle* clone() const { return new circle(radius);
}
} class filled_circle: public shapeС { public: filled_circle* clone() const { return new filled_circle(radius, color);
}
}
Эта функция является виртуальной и для каждого наследника создаёт и возвращает объект соответствующего класса. Клонирование является по- лиморфным, так как объект должен клонировать себя, а не объект базового типа. То есть circle клонирует circle, filled_circle клонирует filled_circle. p[2] = p[0]->clone(); p[3] = p[1]->clone();
Следует обратить внимание на то, что деструктор базового класса тоже объявлен виртуальным. virtual shapeС() {}
Важно, чтобы деструктор был виртуальным, если класс будет ис- пользоваться в качестве базового класса.
Если базовый класс не имеет явного деструктора, а у потомков класса появятся явные деструкторы, например, освобождающие динамическую память, то возможна ошибка утечки памяти.
Важно гарантировать, чтобы при уничтожении объекта был вызван деструктор именно того класса-наследника, к которому он относится. Если базовый класс не требует выполнения явного деструктора, не следует пола- гаться на деструктор по умолчанию. Вместо этого необходимо описать виртуальный деструктор с пустой реализацией.
96
Конструкторы не могут быть виртуальными. Производный класс не наследует конструкторы базового класса, поэтому бессмысленно делать их виртуальными.
Статические функции также не могут быть виртуальными или объяв- ляться с модификаторами const или volatile.
2.6. Цена виртуальности и система RTTI Полиморфизм в C++ реализуется с помощью таблиц виртуальных функций — Virtual Methods Table
(VMT
).
Для каждого класса, содержащего
хотя бы одну виртуальную функ- цию, создаётся VMT, которая содержит адреса всех виртуальных функций, как этого класса, так и всех его предков. В каждом объекте такого класса появляется дополнительный указатель vptr на таблицу виртуальных функций. Если в классе и его предках нет виртуальных функций, то в его объекте поле vptr отсутствует (реализуется принцип: не платим за то, что не используем).
В C++ нет общего главного класса-предка, как например, Objectв
PascalABC.Net, C#, Java
. Это делается в целях повышения эффективности.
Так как общий предок предоставляет набор виртуальных функций (мето- дов), что приводит к созданию VMT для каждого класса.
Пусть в классе filled_circle есть функция set_color(). void set_color(int c) {color = c;}
Даже, если мы точно знаем, что в элементе массива p[1] находится указатель на объект класса filled_circle, вызвать функцию set_color() через этот указатель нельзя. p[1]->set_color(10); // ошибка компиляции !!!
97
Нужно выполнить явное приведение типа с помощью операции dynamic_cast <тип> для преобразования указателя на shapeC к ука- зателю на filled_circle. Оператор dynamic_cast может быть при- менён к указателям или ссылкам. dynamic_cast(p[1])->set_color(10);
В отличие от обычного приведения типа в стиле Си, проверка коррект- ности приведения типов в стиле С++ для классов с виртуальными функ- циями производится во время выполнения программы.
Если в классе имеются виртуальные методы, то на этапе выполнения операция dynamic_cast пытается выполнить преобразование к указан- ному типу данных. В случае преобразования указателя к типу данных, ко- торый не является фактическим типом объекта, в результате будет получен нулевой указатель. При работе со ссылками, если преобразование невоз- можно, будет сгенерировано исключение std::bad_cast. Для его обра- ботки операцию dynamic_cast следует поместить в блок try/catch.
Если виртуальных методов в классе и его предках нет, то dynamic_cast будет работать как static_cast.
Операция dynamic_cast использует механизм динамической иден- тификации типа данных RTTI (Runtime Type Identification). RTTI основана на способности системы сообщать о динамическом типе объекта и предос- тавлять информацию об этом типе во время выполнения (в отличие от вре- мени компиляции). RTTI доступен только для классов, которые являются полиморфными, т.е. у них есть хотя бы одна виртуальная функция.
Таким образом, операция dynamic_cast позволяет идентифициро- вать динамический тип переменной во время выполнения. Операция typeid() используется для определения типа переменной во время вы-
98 полнения. Он возвращает ссылку на объект класса std::type_info, ко- торый содержит поля, позволяющие получить информацию о типе. Этот класс содержит перегруженные операции == и !=, а также функцию name().
Следующие проверки идентичны по результатам.
Первый вариант: filled_circle *q = dynamic_cast(p[1]); if (q!=nullptr) q ->set_color(10);
Второй вариант:
#include //требуется для использования typeid() if (typeid(*p[1]).name() == typeid(filled_circle).name()) dynamic_cast(p[1])->set_color(10);
Операция typeid() для полиморфных типов работает полиморф- ным образом — возвращает динамический тип объекта.
Обратите внимание, что результатом вызова функции typeid(*p[1]).name() является строка «class filled_circle», а результа- том вызова typeid(p[1]).name() — «class shapeC *».
2.7.
Отношение подобия
Используя закрытое наследование, можно реализовать отношение
«подобен», или «as-a». В этом случае потомок может воспользоваться при своей реализации средствами предка, не позволяя, однако, ни объектам, ни собственным потомкам их использовать.
Напомним, что C++ рассматривает открытое наследование как отно- шение типа «является». В частности, компиляторы, столкнувшись с иерар- хией открытого наследования, неявно преобразуют указатель или ссылку на объект класса потомка в указатель или ссылку на объект предка, если
99 это необходимо для вызова функций. Например, в рассмотренных приме- рах класс Student открыто наследует классу Person. При этом в случае необходимости, компилятор неявно преобразует указатель или ссылку на объект класса Student в указатель или ссылку на объект класса Person.
В противоположность открытому наследованию компиляторы в слу- чае закрытого наследования не преобразуют указатели или ссылки на объ- екты производного класса в указатели или ссылки на объекты базового класса. Кроме того, члены, наследуемые от закрытого базового класса, ста- новятся закрытыми, даже если в базовом классе они были объявлены как защищенные или открытые. Поэтому для объектов наследника мы не мо- жем вызывать функции предка.
Закрытое наследование означает «реализовано посредством…». Де- лая класс Derived закрытым наследником класса Base, мы заинтересова- ны в использовании уже написанного для Base кода.
Можно сказать, что закрытое наследование
означает наследование од- ной только реализации, без интерфейса. Закрытое наследование ничего не означает в ходе проектирования программного обеспечения и обретает смысл только на этапе реализации.
Таким образом, закрытое наследование — это исключительно прием реализации, который является альтернативой включению (композиции).
Например, класс Derived может не наследовать, а содержать объект клас- са Base.
Если класс Base имеет защищённые (protected) члены, то в слу- чае включения в класс Derived они недоступны для использования во включающем классе. Если же эти члены необходимы классу Derived, то следует применять закрытое наследование.
100
Пример 14. Предположим, что имеется реализация класса Point
«точка на прямой». Использовать этот класс при реализации класса
GreenHopper «исполнитель Кузнечик из задач ЕГЭ по информатике». С его помощью решить следующую задачу. Кузнечик может перемещаться по числовой оси с помощью команды jump(N), где N — любое целое чис- ло. Кроме того, он может сообщать о своём положении на числовой оси с помощью команды WhereAreYou(). Кузнечик выполнил программу из
50 пар команд: jump(5), jump(-3). На какую одну команду можно заме- нить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы. class Point { private: int x; public:
Point(int x = 0) : x(x){} protected: void setx(int newx) { x = newx;
} int getx() { return x;
}
};
По условию задачи в основу решения должен быть положен предло- женный класс Point. Использование открытого наследования невозможно вследствие требования, что кузнечик должен понимать только две команды jump(N) и WhereAreYou(). Использование включения не позволяет об- ращаться к функциям setx(N) и getx(), поскольку они объявлены как protected. Единственным вариантом решения является закрытое насле- дование (рис.2.6).
101
Рис. 2.6. UML диаграмма классов к примеру 12
#include using namespace std; class GreenHopper : private Point { public:
GreenHopper(int x=0) :Point(x) {} void jump(int dx) { setx(getx()+dx);
} int WhereAreYou() { return getx();
}
}; int main() {
GreenHopper G;
//cout< G.jump(5);
G.jump(-3);
} cout << "jump(" << G.WhereAreYou() - t << ")"<}
Пример 15. Используя готовую реализацию класса «список целых чисел», создать класс «стек целых чисел». class error{}; class list{ private:
// внутренняя организация класса может быть разной
102 public: list();
list(); bool isEmpty() const; void inHead(int val); void inTail(int val); int getFirst()const throw (error); int getLast()const throw (error); void delFirst()throw (error); void delLast()throw (error);
//в полной реализации могут быть еще функции
};
Теперь реализуем класс «стек» (рис. 2.7). class Stack:private list{ public:
Stack():list(){} bool isEmpty(){ return list::isEmpty();
} void push(int i){ inHead(i);
} int top() const throw (error);{ return getFirst();
} int pop throw (error); (){ int res=getFirst(); delFirst(); return res;
}
};
Рис. 2.7. UML диаграмма классов к примеру 13
103
Использование закрытого наследования позволило в этом примере скрыть возможности базового класса и тем самым защитить стек от некор- ректного использования. Например, нельзя попытаться вынуть элемент
«снизу» из стека.
Приведем текст основной программы. int main() {
Stack p; for (int i=0;i<10;i++) p.push(i); while (!p.isEmpty()) cout<
return 0;
}
Для проверки работоспособности основной программы необходимо иметь реализацию класса «список целых чисел». Создать реализацию клас- са на базе массива.
Реализовать класс стек, используя принцип включения, а не закрыто- го наследования.
2.8.
Коллекции и итераторы
Коллекция или контейнер — объект программы, содержащий в себе набор значений одного или различных типов и позволяющий обращаться к этим значениям.
Термин «объект» в данной книге используется в двух смыслах: про- граммный объект и экземпляр класса. С точки зрения коллекции — это программный объект.
Назначение коллекции — служить хранилищем программных объек- тов и обеспечивать доступ к ним. Обычно коллекции используются для
104 хранения групп однотипных объектов, подлежащих стереотипной обработ- ке. Для обращения к конкретному элементу коллекции могут использовать- ся различные функции, в зависимости от ее логической организации. Реа- лизация может допускать выполнение отдельных операций над коллекция- ми в целом. Наличие операций над коллекциями во многих случаях может существенно упростить программирование.
Примерами коллекций являются классы для реализации массива, строки, списка.
Итератор — объект, позволяющий программисту перебирать все элементы коллекции без учета особенностей ее реализации.
В простейшем случае итератором в низкоуровневых языках является указатель. Операцию индексирования можно считать примитивной формой итератора. Необходимо отметить, что счётчик цикла иногда называют ите- ратором цикла. Тем не менее, счётчик цикла обеспечивает только перебор элементов, но не доступ к элементу.
Использование итераторов в обобщённом программировании позво- ляет реализовать универсальные алгоритмы работы с контейнерами. При- мерами коллекций (контейнеров), по которым может перемещаться итера- тор, могут быть: список, очередь, множество, ассоциативный массив и др.
Итератор похож на указатель своими основными операциями: указа- ние одного отдельного элемента в коллекции объектов (доступ к элементу) и изменение своего значения так, чтобы указывать на следующий элемент
(перебор элементов). Также должен быть определён способ создания ите- ратора, указывающего на первый элемент коллекции, и способ узнать, дос- тигнут ли конец коллекции. В
зависимости от используемого языка и цели, итераторы могут поддерживать дополнительные операции или определять различные варианты поведения.
105
Главное предназначение итераторов заключается в предоставлении возможности пользователю обращаться к любому элементу контейнера при сокрытии внутренней структуры контейнера от пользователя. Это позволя- ет контейнеру хранить элементы любым способом при допустимости рабо- ты пользователя с ним как с простой последовательностью или списком.
Проектирование класса итератора тесно связано с соответствующим клас- сом контейнера. Обычно контейнер предоставляет функции создания ите- раторов.
Существует множество разновидностей итераторов, различающихся своим поведением, включая: однонаправленные, обратные (реверсные) и двунаправленные итераторы; итераторы ввода и вывода; константные итераторы (защищающие контейнер или его элементы от изменения).
В тех случаях, когда коллекция представляет собой структуру, осно- ванную на указателях, итератор может быть реализован в виде дополни- тельного поля — текущего указателя. В этом случае следует заботиться о его состоянии при любых модификациях коллекции, даже если его не придётся использовать. Кроме того, такой встроенный итератор обычно только один, а могут возникнуть задачи, в которых потребуется наличие двух, трёх или даже большего количества итераторов.
Итераторы-объекты имеют преимущество по сравнению со встроен- ным текущим указателем, так как позволяют создавать для одной коллек- ции любое количество итераторов, действующих независимо. Таким обра- зом, итератор позволяет вынести рабочий указатель за пределы коллекции, но при этом дает возможность перемещаться по объектам, содержащимся в коллекции, аналогично тому, как текущий указатель позволяет переме- щаться внутри коллекции.
106
Как правило, итератор имеет операцию доступа к элементу коллек- ции по ссылке. Такая операция может быть реализована путём перегрузки операции разыменования *. Для итераторов предусматриваются также опе- рации перемещения вперёд и назад по коллекции объектов. Чаще всего для этого перегружаются операции ++ и –-. Кроме того, операции = = и ! = обычно перегружаются для проверки равенства итераторов. В классе кол- лекции для использования итератора обычно создаются две функции: iterator begin() – инициализация итератора ссылкой на первый элемент коллекции; iterator end() – значение, сообщающее, что итератор достиг конца коллекции.
Через итератор могут быть реализованы другие операции над кол- лекцией, например, вставка элемента после позиции итератора или удале- ние элемента в позиции итератора. При реализации таких операций очень важно оговорить правила поведения итератора после выполнения опера- ции.
Пример 16. Реализовать линейный двусвязный список и итератор для него с возможностью перемещения в двух направлениях.
Класс список List содержит элементы, описываемые структурой node: struct node{ int data; node* next; node* prev; node(int data, node* next, node* prev) { this->data = data; this->next = next; this->prev = prev;
}
};
107
Для упрощения в дальнейшем вывода элементов списка перегружена операция вывода в поток. Для структуры не требуется объявлять её друже- ственной. ostream & operator<<(ostream & out, const node& X) { out << X.data; return out;
}
Чтобы в определении класса List операции begin() и end() могли возвращать объекты типа итератор списка, нужно сделать предвари- тельное объявление класса итератора. class listIterator;
Это связано с рекурсией в определении классов коллекции List и итератора listIterator.
Определение класса List: class List{ public: class Error { public: void what(){ cout << "List is empty" << endl;
}
};
List() { head = 0; tail = 0;
}
List(const List& l);
List(); bool isEmpty() const; void inHead(int val); void inTail(int val); int getFirst()const; int getLast()const; void delFirst(); void delLast(); listIterator begin() const; listIterator end() const; friend ostream& operator<<(ostream & os, const List& l);
//в полной реализации могут быть еще методы
108 private: node* head; node* tail;
Error err;
};
Определение класса итератора для списка: class listIterator { public: class Error { public: void what(){ cout << "Iterator error" << endl;
}
}; private: const List *collection; node *cur; public: listIterator(const List *s, node *e) :collection(s), cur(e){} const int operator *(){ return cur->data;
} listIterator operator++(); //префиксный ++ listIterator operator--(); //префиксный -- int operator == (const listIterator &ri) const; int operator != (const listIterator &ri) const;
};
Реализация класса list для двусвязного списка:
List::List(const List& l) { head = 0; tail = 0; node* q = l.head; while (q){ inTail(q->data); q = q->next;
}
}
List::List(){ while (head){ node* cur = head; head = head->next; delete cur;
} tail = head = nullptr;
} bool List::isEmpty() const { return (head == nullptr);
}
109 void List::inHead(int val){ node* t = new node(val,head,nullptr); if (!head) tail = t; else head->prev = t; head = t;
} void List::inTail(int val){ node* t = new node(val, nullptr,tail); if (head){ tail->next = t; tail = t;
} else{ head = tail = t;
}
} int List::getFirst() const{ if (head) return head->data; else throw err;
} int List::getLast()const{ if (head) return tail->data; else throw err;
} void List::delFirst(){ if (head){ node *t = head; head = head->next; head->prev = nullptr; delete t;
} else throw err;
} void List::delLast(){ if (head){ if (head == tail) { delete tail; head = nullptr; } else { node *t = head; while (t->next != tail)
110 t = t->next; delete tail; tail = t; t->next = nullptr;
}
} else throw err;
} ostream& operator<<(ostream & os, const List& l){ node *p = l.head; while (p) { os << *p << " "; p = p->next; } os << endl; return os;
}
Реализация класса listIterator для итератора двусвязного списка: listIterator listIterator:: operator++() { if (cur) { cur = cur->next; return *this;
} else throw Error();
} listIterator listIterator:: operator--() { if (cur) { cur = cur->prev; return *this;
} else throw Error();
} int listIterator:: operator==(const listIterator &ri) const { return ((collection == ri.collection) && (cur == ri.cur));
} int listIterator:: operator!=(const listIterator &ri) const { return !(*this == ri);
} listIterator List::begin() const { return listIterator(this, head);
} listIterator List::end() const { listIterator iter(this, nullptr); return iter;
}
111
В закрытых полях класса хранится указатель на коллекцию, с кото- рой работает итератор и указатель на текущее положение итератора в кол- лекции. Конструктор с параметрами позволяет инициализировать эти поля.
Структуры
являются открытыми классами с открытым доступом, по- этому возможно обращение к полям структуры, представляющей элемент списка напрямую. Если бы элемент списка был представлен классом с за- крытыми полями, для доступа к ним пришлось бы использовать соответст- вующие функции или класс итератора нужно было бы объявить дружест- венным классу элемента списка.
Чтобы использовать итератор для работы с классом-коллекцией, не- обходимо, чтобы класс содержал функции инициализации итератора: listIterator begin() const; listIterator end() const;
Инициализация итератора ссылкой на первый элемент списка осуще- ствляется следующей функцией: listIterator list::begin() const { return listIterator (this,head);
}
В качестве параметров конструктору итератора передаются указатель на объект-список, для которого будет создан итератор, и указатель на голо- ву списка.
Функция listIterator list::end() const возвращает значе- ние, которое является признаком того, что итератор достиг конца списка: listIterator list::end() const { listIterator iter(this,nullptr); return iter;
}
Функцию end() нельзя заменить простым сравнением указателя с nullptr
, так как в операциях == и != для итератора прежде всего прове- ряется, относятся ли два итератора к одному и тому же списку.
112
Рассмотрим использование итератора для линейного двусвязного списка на примере нескольких функций.
Нахождение суммы элементов списка, расположенных между двумя итераторами. int sum(listIterator b, listIterator e) { int sum = 0; while (b != e){ sum+= *b;
++b;
} return sum;
}
Нахождение итератора, ссылающегося на максимальный элемент списка. listIterator max(listIterator b, listIterator e) { listIterator maxx = b; while (b != e){ if (*b > *maxx) maxx = b;
++b;
} return maxx;
}
Вывод в обратном порядке элементов списка, расположенных между двумя итераторами. void reverseprint(listIterator b, listIterator be){ while (b!=be) { cout << *(--be) << ' ';
} cout << endl;
}
Ниже приведён код для тестирования созданных функций. int main(){
List l1; for (int i = 0; i < 5;++i) l1.inHead(i); for (int i = 5; i < 10; ++i) l1.inTail(i);
List l2(l1); cout << " list \n" << l2 << endl; cout << sum(l2.begin(), l2.end())<
113 listIterator mt = max(l2.begin(), l2.end()); cout << *mt << endl; reverseprint(mt,l2.begin()); reverseprint(mt, l2.end()); return 0;
}
2.9.
Классы для рекурсивных типов данных
Рекурсивное определение данных возникает, когда структура данных ссылается на объект такой же структуры. При этом в случае одной ссылки чаще всего в алгоритмах обработки эффективней использовать итерацию.
Если же ссылок больше одной (как в деревьях), то в большинстве случаев применяются рекурсивные реализации. Рекурсия помогает разрабатывать изящные и эффективные структуры данных и алгоритмы в тех случаях, ко- гда решение без использования рекурсии оказывается сложным и неоче- видным.
Рекурсивное определение бинарного дерева можно реализовать как класс, содержащий внутри себя указатель на узел дерева (корень) и рекур- сивное описание узла дерева. При этом открытые функции-члены класса не будут рекурсивными. Второй способ определения класса бинарного дерева состоит в том, чтобы определить в нём указатели на два поддерева и от- крытые рекурсивные функции для работы с деревом.
Для демонстрации этих двух подходов определим классы с мини- мально необходимым количеством функций-членов.
Пример 17. Реализовать класс бинарного дерева поиска, определив в нём указатели на два поддерева и открытые рекурсивные функции для ра- боты с деревом: конструктор, конструктор копии, деструктор, добавление элемента в дерево и вывод всех элементов дерева в поток. class TreeR{ private: int data;
TreeR *lt, *rt;
114 public:
TreeR (int val=0, TreeR *l = nullptr, TreeR *r = nullptr): data(val), lt(l), rt(r) {}
TreeR(const TreeR * t){ if (t->lt) lt = new TreeR(t->lt); data = t->data; if (t->rt) rt = new TreeR(t->rt);
}
TreeR(){ if (lt != nullptr) delete lt; if (rt != nullptr) delete rt;
} void add(int a){ if (data > a){ if (lt) lt->add(a); else lt = new TreeR(a);
} else{ if (rt) rt->add(a); else rt = new TreeR(a);
}
} friend ostream& operator<<(ostream& os, const TreeR *t){ if (t->lt) os << t->lt; os << t->data << " "; if (t->rt) os<< t->rt; return os;
} void printRKL(){ if (rt) rt->printRKL(); cout << " " << data << " "; if (lt) lt->printRKL();
}
};
В данном примере вывод в поток реализован двумя способами: пере- грузкой операции выдачи в поток << и функцией printRKL.
В перегруженную операцию << указатель на дерево передаётся пара- метром, посредством которого реализуются рекурсивные вызовы. friend ostream& operator<<(ostream& os, const TreeR *t)
Аналогично реализуется рекурсия и в функции printRKL, в кото- рую указатель на дерево передаётся через неявный параметр this.
115 if (rt) rt->printRKL();
//эквивалентно if (this->rt) this->rt->printRKL();
При использовании класса TreeR приходится объявлять переменную указатель на объект и создавать объект динамически. При этом конструк- тор без параметров создаёт не пустое дерево, а дерево с одной вершиной, имеющей значение по умолчанию.
TreeR *t= new TreeR();// это непустое дерево t->add(5); t->add(-7); t->add(3); t->add(-4); cout <<"T "<< t << endl; t->printRKL();
TreeR *t1 = new TreeR(t); cout << "T1 "<Для класса TreeR пустота дерева определяется не на уровне класса, а на уровне указателя на объект класса.
TreeR* t0= nullptr; // это пустое дерево
Поэтому нельзя реализовать функцию-член класса для проверки на пустоту. Для безопасной работы перед вызовом функций-членов класса следует выполнять проверку на пустоту следующим образом: if (t0!=nullptr) t0->add(3); if (t0!=nullptr) t0->RKL(); if (t0!=nullptr) cout <<"T "<< t0 << endl;
Для динамических объектов при выполнении операции delete вы- зывается деструктор, но указатель на объект не обнуляется. Если предпола- гается дальнейшее использование указателя, ему необходимо явно присво- ить значение nullptr. if (t!=nullptr){ delete t; t=nullptr;
}
116
При использовании операции удаления отдельных узлов из дерева возникает
проблема при удалении последней вершины, которая не может быть решена в самой операции.
Пример 18. Реализовать класс бинарного дерева поиска, содержащий внутри себя указатель на узел дерева (корень) и рекурсивное описание узла дерева. Определить открытые функции-члены класса: конструктор, конст- руктор копии, деструктор, добавление элемента в дерево и вывод всех эле- ментов в поток. При их реализации использовать рекурсивные функции в закрытой части описания класса. class Tree{ private: struct TNode; typedef TNode* node_ptr; struct TNode{ int data; node_ptr lt, rt;
TNode (int val, node_ptr l=nullptr, node_ptr r=nullptr): data(val), lt(l), rt(r){}
}; node_ptr root; void delTree(node_ptr t){ if (t!=nullptr){ delTree(t->lt); delTree(t->rt); delete t;
}
} void add(node_ptr& t, int a){ if (t == nullptr) t = new TNode(a); else if (t->data > a) add(t->lt, a); else add(t->rt, a);
} void printLKR(node_ptr t, ostream& os) const{ if (t){ printLKR(t->lt, os); os << t->data << " ";
117 printLKR(t->rt, os);
}
} void copy(node_ptr t, node_ptr &newT) const { if (t != nullptr){ newT = new TNode(t->data, 0, 0); copy(t->lt, newT->lt); copy(t->rt, newT->rt);
} else newT = nullptr;
} public:
Tree(): root(nullptr) {}
Tree(const Tree& t){ copy( t.root, root);
}
Tree(){ delTree (root);
} void addNode(int a){ add(root, a);
} friend ostream& operator<<(ostream& os, const Tree &t){ t.printLKR(t.root,os); return os;
}
};
В примере типы TNode для узла дерева и node_ptr для указателя на узел определены внутри класса, что подчёркивает инкапсуляцию внут- ренней организации класса Tree. Именно в определении типа TNode присутствует рекурсия. Поэтому рекурсивные функции оперируют с указа- телями на узел дерева и должны быть объявлены как private. Для досту- па к ним используются открытые функции класса, которые вызывают ре- курсивные функции, передавая в качестве параметра указатель на корень дерева.
118
Такое описание класса допускает существование пустого дерева.
Конструктор без параметров создаёт пустое дерево. Если предусмотреть операцию удаления узла дерева, то можно получить в процессе её выпол- нения пустое дерево. Для безопасной работы с таким деревом рекоменду- ется иметь операцию проверки дерева на пустоту.
Tree t; t.addNode(5); t.addNode(7); t.addNode(3); t.addNode(4); cout <<"T "<< t << endl;
Tree t1(t); cout << "T1 "<Очевидно, что реализация класса бинарного дерева в примере 18 ли- шена недостатков, перечисленных в примере 17. Именно такой способ реа- лизации рекомендуется использовать при создании классов для рекурсив- ных структур.
Скачать 1.49 Mb.