Пособие по ооп. С++ ООП УчебноеПособие. Объектноориентированное

• Название: Объектноориентированное
• Анкор: Пособие по ооп
• Дата: 23.11.2021
• Размер: 1.49 Mb.
• Имя файла: С++ ООП УчебноеПособие.pdf
• Тип: Учебное пособие; #279608
• страница: 6 из 7

ГЛАВА 3.
ОБОБЩЕННЫЙ ПОДХОД
Одной из важнейших целей объектно-ориентированного программи- рования является поддержка повторного использования кода. Один из ме- ханизмов для достижения этой цели — шаблоны С++. Шаблоны функций, которые были рассмотрены в книге Демяненко Я.М., Чердынцевой М.И.[2], позволяют избавиться от множественной перегрузки функций. При этом обобщается один и тот же алгоритм для разных типов данных. Этот подход относится к обобщённому программированию.
Обобщённое программирование (generic programming) заключается в описании структур данных и алгоритмов в терминах типов, подставляемых в качестве параметров в эти алгоритмы и структуры. Обобщённое про- граммирование является одним из проявлений полиморфизма. Обобщён- ный подход в языке С++ основывается на шаблонах функций и шаблонах классов.
3.1.
Шаблоны классов
Шаблоны классов, так же как и шаблоны функций, являются трафа- ретами, по которым компилятор создает шаблонные классы и шаблонные функции.
Шаблоны классов часто называют параметризованными типами, так как они имеют один или большее количество параметров типа, опреде- ляющих настройку шаблона класса на специфический тип данных при соз- дании объекта класса.
Например, шаблон класса Stack может служить основой для созда- ния многочисленных классов Stack: «Stack для данных типа int»,
«Stack для данных типа double», «Stack для данных типа Time» и т. д.

120
Пример 19. Создать шаблон класса Stack с реализацией на основе массива.
//Шаблон класса Stack файл stack.h
#ifndef TSTACK_H
#define TSTACK_H
#include class stackEmpty {
}; class stackFull {
}; template class Stack { private:
T * start;
//указатель на стек int head;
//положение вершины стека int size;
//размер стека public:
//конструктор с параметром по умолчанию для размера стека
Stack(int = 10);

Stack() { delete[] start; }
//деструктор void push(const T&); //добавление элемента в стек
T pop();
//извлечение элемента из стека
T top();
//просмотр элемента на вершине стека bool isEmpty() const { //true, если стек пустой return head == -1;
} bool isFull() const { //true, если стек полон return head == size - 1;
}
};
//конструктор template
Stack::Stack(int n) {
//определение «разумного» размера стека size = n>0 && n<1000 ? n : 10; start = new T[size]; head = -1;
}
// добавление объекта в стек
//в случае переполнения стека выбрасывается исключение template void Stack::push(const T& x) {

121 if (isFull()) throw stackFull(); start[++head] = x;
}
//извлечение элемента из стека template
T Stack::pop() { if (isEmpty()) throw stackEmpty();
T x = start[head--]; return x;
}
// просмотр элемента на вершине стека template
T Stack::top() { if (isEmpty()) throw stackEmpty();
T x = start[head]; return x;
}
#endif
Определение шаблона класса Stack похоже на определение класса, только впереди добавляется конструкция: template
Добавленная к заголовку конструкция template указывает на то, что описывается шаблон класса Stack с параметром ти- па T. Идентификатор T определяет тип данных-элементов, хранящихся в стеке, и может использоваться при описании типов полей класса и в функ- циях-членах класса.
Компилятор рассматривает все функции-члены класса как шаблоны функций, параметры которых совпадают с параметрами шаблона класса.
Поэтому каждое определение функции-члена класса вне шаблона класса начинается с конструкции: template
Внешнее определение каждой функции-члена шаблона класса ис- пользует операцию разрешения области видимости с именем шаблона класса Stack.

122

Хорошей идеей является написать и протестировать конкретный класс, а затем преобразовать его в шаблон. Таким образом, можно решить многие проблемы проектирования и обнаружить большую часть ошибок кода в тексте конкретного класса.
Аналогично шаблонам функций, все шаблоны классов и структур должны быть помещены в заголовочные файлы. Для шаблонов классов в отличие от просто классов выносить реализации их членов-функций в от- дельный *.cpp файл нельзя. Это связано с тем, что шаблоны в языке С++ не компилируются, потому что шаблон представляет собой не фрагмент про- граммного кода, а лишь инструкции для построения кода.
Для шаблонов классов и структур код генерируется в момент опреде- ления объекта. Причём генерируются только те члены-функции класса, ко- торые используются.
Подстановка конкретного типа в шаблон приводит к созданию шаб- лонного класса, т.е. к инстанцированию шаблона (template instantiation).
Аналогично функция инстанцируется (генерируется, конкретизируется) из шаблона функции и аргумента шаблона. Использование различных терми- нов для одного понятия связано с терминологическими проблемами, воз- никающими при переводе. О них мы уже говорили в книгах Демянен- ко Я.М., Чердынцевой М.И.[2] и Русанова Я.М., Чердынцева М.И.[6].
Количество инстанций зависит от количества используемых типов.
Версия шаблона для конкретного аргумента шаблона называется специали- зацией. Только специализации шаблонов содержат настоящий код. Генера- ция версий шаблона для набора аргументов шаблона является задачей ком- пилятора, а не программиста.
По умолчанию, шаблон предоставляет единственное определение, которое должно использоваться для всех аргументов шаблона. Явная спе-

123 циализация позволяет обеспечить альтернативные реализации шаблона.
Выделяют специализации, определяемые пользователями, или просто пользовательские специализации. Например, если для специфического типа данных нужен класс, который не соответствует общему шаблону класса, можно явно определить его, отменив тем самым действие шаблона для это- го типа.
Так шаблон класса Stack может использоваться практически для любого типа. Однако может возникнуть необходимость создать специфи- ческий класс Stack для некоторого типа, например, Specific. Для это- го нужно просто создать новый класс с именем Stack.
Stack{
...//определение специфического стека
}

В C++ разрешаются все действия с типом T. Поэтому если при инстан- цировании будет использован тип, для которого не определены какие- нибудь операции, используемые в шаблоне, то возникнет ошибка компиля- ции шаблонного класса или шаблонной функции. А в .NET и Java сущест- вуют возможность введения ограничения на тип, с которым можно инстан- цировать шаблон. Тем самым повышается надёжность использования обобщённых типов.

В С++ в результате компиляции шаблона получается исполняемый код инстанцированных функций, структур и классов. В .NET в результате ком- пиляции обобщения создается исполняемый код самого обобщения, т.е в
.NET можно создать dll с обобщенным классом.
Рассмотрим текст программы, в которой используется шаблон класса
Stack.
#include
#include "stack.h"

124 using namespace std; int main() {
Stack intStack(5); for (int i = 0; i<5; i++) intStack.push(10 - i); cout << intStack.top() << endl; while (!intStack.isEmpty()) cout << intStack.pop() << ' '; cout << endl; return 0;
}
Объект intStack объявляется как экземпляр класса Stack
(произносится как «Stack типа int»). При генерации исходного кода для класса Stack типа int компилятор заменит параметр T на тип int.
Когда создается объект intStack типа Stack, конструктор класса Stack создает массив элементов типа int, представляющий эле- менты данных стека. Компилятор замещает оператор start=new T[size]; в описании шаблона класса Stack оператором start=new int[size]; в шаблонном классе Stack.
Шаблон класса Stack использовал только один параметр типа в за- головке шаблона. Но в шаблонах имеется возможность использования лю- бого количества параметров. Кроме параметров типа, могут использоваться и нетиповые параметры. Например, заголовок можно модифицировать, указав в нем нетиповой параметр int elements для задания размера стека:
//заголовок для шаблона класса StackParam
//аналога шаблона класса Stack template class StackParam { private:
T start [elements];
// массив для размещения данных стека int head;
//положение вершины стека int size;
//размер стека

125 public:
StackParam ():size(elements),head(-1){}
//конструктор
StackParam () {}
//деструктор void push(const T&);
//добавление элемента в стек
T pop();
//извлечение элемента из стека
T top();
//просмотр элемента на вершине стека bool isEmpty() const { //true, если стек пустой return head == -1;
} bool isFull() const { //true, если стек полон return head == size - 1;
}
};
Тогда объявление типа
StackParam intStack1; приведет к созданию во время компиляции шаблонного класса
StackParam с именем intStack1, состоящего из 100 элементов данных типа int
Этот шаблонный класс будет иметь тип
StackParam.
В описании класса в разделе закрытых данных-членов помещено сле- дующее объявление массива:
T start [elements]; //массив для размещения данных стека
Поэтому необходимость выделение динамической памяти под массив в конструкторе и освобождение её в деструкторе отпадает.
Если размер класса контейнера, например, массива или стека, может быть определён во время компиляции (например, при помощи нетипового параметра шаблона, указывающего размер), это устранит расходы при ди- намическом выделении памяти во время выполнения программы.

Определение размера класса контейнера во время компиляции (напри- мер, через нетиповой параметр шаблона) исключает возможность возник- новения потенциально неисправимой ошибки во время выполнения про- граммы, если оператору new не удастся получить необходимое количество памяти.

126
Поскольку у шаблона класса изменился список параметров, необхо- димо внести изменения в определение шаблонов членов-функций класса.
// добавление объекта в стек
//в случае успеха возвращается true, в противном случае false template void StackParam::push(const T& a) { if (isFull()) throw stackFull(); start[++head] = a; //элемент помещается в стек
}
//выталкивание элемента из стека template
T StackParam::pop() { if (isEmpty()) throw stackEmpty();
T a = start[head--]; //элемент выталкивается из стека return a;
}
//просмотр элемента из вершины стека template
T StackParam::top() { if (isEmpty()) throw stackEmpty();
T y = start[head]; //элемент выталкивается из стека return y;
}
Пример 20. Дана символьная строка, содержащая латинские буквы, цифры и четыре вида скобок: ( ),[ ],{ }, < >. Проверить правильность рас- становки скобок — каждой открывающей соответствует закрывающая скобка того же вида. Для решения задачи необходимо использовать стек.
Воспользуемся шаблоном класса StackParam.
#include
#include
#include "paramstack.h" using namespace std; class unpair {}; class missRight{}; int main() { locale::global(locale("")); string str; cin >> str;

127 string left = "([{<"; string right = ")]}>";
StackParam St; char q; int pr; try { for (char c : str) { if (left.find(c) != string::npos)
St.push(c); else { pr = right.find(c); if (pr != string::npos) { q = St.pop(); if (pr != left.find(q)) throw unpair();
}
}
} if (!St.isEmpty()) throw missRight(); cout <<"скобки расставлены верно" << endl;
} catch (stackEmpty) { cout << "не хватает левой скобки" << endl;
} catch (unpair) { cout << "непарные скобки" << endl;
} catch (missRight) { cout << "не хватает правой скобки" << endl;
} return 0;
}
Принцип проверки основан на том, что каждая открывающаяся скоб- ки заносится в стек, а каждая закрывающаяся выталкивает из стека элемент
— открывающуюся скобку. Полученная пара проверяется на соответствие.
При этом возможны три ошибочные ситуации, которые обрабатыва- ются с помощью исключений.
3.2.
Коллекции
Пример 21. Реализовать шаблон класса «Линейный односвязный список». Для списка использовать ссылочную организацию.

128
Воспользуемся для создания шаблона линейного списка шаблоном структуры node: template struct node {
T data; node* next; node(T data, node* next) { this->data = data; this->next = next;
}
}; template ostream & operator << (ostream & out, const node & x) { out << x.data; return out;
}
Шаблон конструктора node содержит два параметра для заполнения информационной и ссылочной частей. node(T data, node* next) { this->data = data; this->next = next;
}
Такая форма конструктора позволяет легко добавлять новый узел в любое место списка. Например:
//создание единственного элемента pn1 node* pn1 = new node(5, nullptr);
//добавление элемента перед pn1 node* pn2 = new node(5, pn1);
//добавление элемента за pn1 pn1->next = new node(7, nullptr);
Шаблон перегруженной операции вывода в поток для шаблона структуры node в поток не требуется объявлять дружественным, посколь- ку по умолчанию в структуре все поля открыты. При этом имя параметра типа в шаблоне не обязано совпадать с именем параметра в шаблоне струк- туры. В нашем примере используются Q и T. template ostream & operator << (ostream & out, const node & x) { out << x.data; return out;
}

129
Теперь, используя шаблон структуры node, описываем шаблон клас- са list для реализации линейного односвязного списка. template class list{ private: node* first; node* last; error err; public: list(): first(nullptr), last(nullptr) {
}
list(); bool isEmpty() const; void addFirst(T x); void addLast(T x);
T getFirst()const;
T getLast()const;
T delFirst();
T delLast();
//Обработка с предикатом int kol(bool(*f) (T)); void for_each(void(*action)(T&)); template friend ostream & operator<< (ostream &out, const list &y);
//в полной реализации могут быть еще функции
};
Поскольку в процессе работы возможно возникновение исключи- тельных ситуаций, создаём пустой класс error. class error{};
Реализация деструктора и функции проверки на пустоту не содержат никаких особенностей. template list::list(){ while (first){ node* cur = first; first = first->next; delete cur;
} last = first = nullptr;
} template bool list::isEmpty() const { return (first == nullptr);
}

130
Обратим внимание на объявление шаблона дружественной функции.
Имя параметра шаблона дружественной функции может быть любым. Что- бы это подчеркнуть мы использовали имя Q, хотя могли оставить T. template friend ostream & operator<< (ostream &out, const list &y);
При этом в описании реализации шаблона дружественной функции не обязательно использовать то же самое имя параметра шаблона. template ostream & operator << (ostream & out, const list & y) { node* p = y.first; while (p) { out << *p<<" "; p = p->next;
} return out;
}
В шаблоне функции добавления элемента в начало списка использу- ем шаблон конструктора структуры node. В качестве значения второго па- раметра используем указатель на начало списка first. При этом если список пуст, выполняется инициализация не только указателя first, но и указателя last. template void list::addFirst(T x){ first = new node(x, first); if (!last) last = first;
}
Обратите внимание, что добавление в конец имеет более сложный алгоритм. template void list::addLast(T x){ if (first){ last->next = new node(x, nullptr); last = last->next;
} else first = last = new node(x, nullptr);
}

131
В шаблонах функций чтения первого и последнего элементов списка возможны ошибки доступа в случае, если список пуст. При этом выбрасы- вается исключение. Выбрасываемый объект err класса error объявлен в закрытой части шаблона класса list. template
T list::getFirst() const{ if (first) return first->data; else throw err;
} template
T list::getLast()const{ if (first) return last->data; else throw err;
}
Функции удаления первого и последнего элементов списка в качестве результата возвращают значение удалённого элемента. В случае пустого списка они выбрасывают исключение. template
T list::delFirst(){
T x; if (first){ x = first->data; node*t = first; first = first->next; delete t; return x;
} else throw err;
} template
T list::delLast(){
T x; if (first){ x = last->data; node*t = first; while (t->next != last) t = t->next;

132 delete last; last = t; last->next = nullptr; return x;
} else throw err;
}
Шаблон функции int kol(bool(*f)(T)) реализует подсчёт ко- личества элементов, для которых выполняется условие, задаваемое одно- местным предикатом. Предикат задаётся указателем на функцию, соответ- ствующую типу bool(*f)(T).
//Обработка с предикатом template
// f — переменная типа "указатель на функцию" int list::kol(bool(*f) (T)) { int k = 0; for (node* p = first; p; p = p->next) if (f(p->data)) k++; return k;
}
В качестве примера такой функции для специализации шаблона спи- ска типом int использована функция проверки на нечётность. bool odd(int x){ return x % 2 != 0;
}
Шаблон функции void for_each(void(*action)(T&)) реали- зует применение функции action к информационному полю каждого элемента списка. Параметр action является указателем на функцию, со- ответствующую типу void(*action)(T&). template
// action — переменная типа "указатель на функцию" void list::for_each(void(*action)(T&)) { node* p = first; while (p) { action(p->data); p = p->next;
}
}

133
В качестве примера такой функции для специализации шаблона спи- ска типом int использована функция удвоения значения. void mult2(int & x) { x *= 2;
}
В функции main использованы специализации шаблона списка ти- пами int и char. int main(void){ list l1; l1.addFirst(3); l1.addLast(4); l1.addLast(99); cout << l1< *l2 = new list; l2->addFirst('1'); l2->addLast('q'); l2->addLast('a'); cout << *l2 << endl; cout << *l2 << endl; cout << l2->delFirst() << endl; cout << *l2 << endl; cout << l2->delLast() << endl; cout << *l2 << endl; return 0;
}