Практическая работа № 1.22. Использование основных шаблонов Цель работы: область применения основных шаблонов Теоретический материал Любая структура данных и алгоритмы имеют дополнительную ценность, если они могут хранить и работать с данными различных типов. Такая универсальность (или что одно и то же, независимость от данных) может быть достигнута в Си++ различными способами: · в обычном Си (см. 9.3) «переход от типа к типу» и абстрагирование от конкретного хранимого типа возможно на основе преобразования типов указателей и использования указателя void*, олицетворяющего «память вообще». Совместно с механизмом динамического связывания возможно создание алгоритмов, в которых фрагмент, ответственный за работу с конкретным типом данных, передается через указатель на функцию;
90 · в Си++ на основе полиморфизма (виртуальных функций) возможно создание интерфейсных классов, способных объединять единым механизмом доступа различные классы. Если эти классы являются «обертками» известных типов данных, то независимость от типов хранимых данных можно обеспечить ссылками на интерфейсный класс. Однако приведенные выше способы не обеспечивают синтаксической совместимости, т.е. они реализуются как технологические приемы, а не как элементы языка. По аналогии с переопределением операций (см. 10.3) хотелось бы использование естественного синтаксиса, где вместо int, double и т.п. фигурировало бы абстрактное обозначение типа, например, T. Такое средство, позволяющее создавать заготовку функции или целого класса, в котором вместо конкретного имени типа данных будет фигурировать его символическое обозначение, называется шаблоном. В первом приближении смоделировать шаблон в обычном Си можно с использованием директив препроцессора для подстановки имен – define. Обозначив именами T и N тип и размерность массива, можно создать класс с использованием этих имен везде, где это необходимо. //-------------------------------------------------------105-01.cpp // Имитация шаблона в обычном Си #define T int // Параметры заданы через подстановку имен #define N 100 // Тип элементов и размерность массива struct Array{ T Data[N]; int k; // Текущее кол-во элементов Array(){ k=0; } // Конструктор - массив пуст void add(T &v){ // Добавление элемента if (k>=N) return; Data[k++]=v;} T remove(int m){ // Удаление элемента по номеру T foo; if (m>=k) return foo; foo=Data[m]; for(int i=m;i Data[i]=Data[i+1]; k--; return foo; } }; void main(){ Array A; int B[10]={6,2,8,3,56,7,89,5,7,9}; for (int i=0;i<10;i++) A.add(B[i]); cout << A.remove(2) << endl; } Чтобы применить ее для другого типа данных, нужно отредактировать директиву define, заменив, например, имя int на double. Но все же основным недостатком этой модели является однократность ее использования. В Си++ текстовая заготовка класса позволяет из одного описания создавать множество классов, отличающихся типом используемых объектов и размерностями данных. Итак, шаблон можно определить как текстовую заготовку определения класса с параметром, обозначающим тип используемых внутри переменных. Сразу же, не дожидаясь описания синтаксиса, отметим особенности трансляции шаблона: · шаблон является описанием группы классов, отличающихся используемым типом данных; · при создании (определении) объекта шаблонного класса указывается тип данных, для которого он создается; · при определении объекта шаблонного класса конкретный тип подставляется в шаблон вместо параметра и создается текстовая заготовка экземпляра класса, которая транслируется и дает собственный оригинальный программный код; · и только затем происходит трансляция определения самого объекта.
91 Самое главное, в отличие от обычных объектов, объект шаблонного класса требует отдельного экземпляра класса для того типа, который обозначен в объекте. Замечание: при чтении транслятором шаблона заголовка класса и шаблонов встроенных в него функций и методов их трансляция не производится. Это происходит в другое время: при трансляции определения объекта шаблонного класса генерируется текстовая заготовка экземпляра класса. Отсюда некоторый нюансы: · чтобы проверить, как транслируется шаблон, нужно описать хотя бы один объект шаблонного класса; · весь шаблон, в том числе и шаблоны методов, следует размещать в заголовочном файле проекта; · на каждый тип данных – параметр шаблона создается отдельный класс и в сегменте команд размещается программный код его методов. Следующим примером попробуем «убить двух зайцев». Во-первых, пояснить довольно витиеватый синтаксис шаблона, а во-вторых, выделить особенности реализации структур данных и использованием технологии ООП. Основной принцип шаблона, добавление к имени класса «довеска» в виде имени – параметра (например, vector). Это имя обозначает внутренний тип данных, который может использоваться в любом месте класса: как указатель, ссылка, формальный параметр, результат, локальная или статическая переменная. Во всем остальном шаблон не отличается от обычного класса. Само имя шаблона (vector) теперь обозначает не один класс, а группу классов, отличающихся внутренним типом данных. //------------------------------------------------------105-02.cpp //----- Шаблон СД - динамический массив указателей template T> class vector{ int sz,n; // Размерность ДМУ и кол-ко элементов T **obj; // Массив указателей на параметризованные public: // объекты типа T T *operator[](int); // оператор [int] возвращает указатель на // параметризованный объект типа T operator int(); // Возвращает текущее количество указателей int append(T*); // Добавление указателя на объект типа T int index(T*); // Поиск индекса хранимого объекта vector(int); // Конструктор vector(){ delete []obj; } // Деструктор }; Данный шаблон может использоваться для порождения объектов-векторов, каждый из которых хранит указатели объекты определенного типа. Имя класса при этом составляется из имени шаблона vector и имени типа данных (класса), который подставляется вместо параметра Т. vector a; vector b; extern class time; vector
92 int index(int *); // Поиск индекса хранимого объекта vector(int); // Конструктор vector(){ delete []obj; } // Деструктор }; Обратите внимание, что это иллюстрация принципа подстановки, а не фрагмент программы с синтаксисом Си++. Далее следует утверждение типа «масло масляное»: встроенные функции (методы) шаблонного класса – есть шаблонные функции. Это означает, что методы класса, включенные в шаблон, также должны «заготовками» с тем же самым параметром, то есть генерироваться для каждого нового типа данных. То же самое касается переопределяемых операторов. //------------------------------------------------------105-02.cpp template vector::operator int() { return n; } template T* vector::operator[](int k){ return k>=n ? NULL : obj[k]; } template int vector::index(T *pobj){ for ( int i=0; i vector::vector(int sz0){ sz=sz0; n=0; obj=new T*[sz]; } template int vector::append(T *pobj){ if (n>=sz) return 0; obj[n++]=pobj; return 1;} Приведенный пример касается только методов, «вынесенных» из заголовка класса. Для каждого из них пишется отдельный шаблон, а сам класс фигурирует в нем под именем вида vector. Возможность непосредственного определения методов в заголовке шаблонного класса (inline-методов) также остается. Шаблоны могут иметь также и параметры-константы, которые используются для статического определения размерностей внутренних структур данных. Кроме того, шаблон может использоваться для размещения не только указателей на параметризованные объекты, но и самих объектов. В качестве примера рассмотрим шаблон для построения циклической очереди ограниченного размера на основе статического массива (см. 6.1), хранящей непосредственно сами объекты (значения, а не указатели). //------------------------------------------------------105-03.cpp //------- Шаблон с параметром-константой template class FIFO{ int fst,lst; // Индексы начала и конца очереди T queue[size]; // Массив объектов класса T размерности size public: T from(); // Функции включения-исключения int into(T); // FIFO(){ fst=lst=0; } // Конструктор }; template T FIFO::from(){ T work=0; if (fst !=lst){ work = queue[lst++]; if (lst==size) lst=0; } return work;} template int FIFO::into(T obj) {
93 if ((fst+1)%size==lst) return 0; // Проверка на переполнение queue[fst++] = obj; if (fst==size) fst=0; return 1; } Объекты такого шаблонного класса при определении имеют два параметра: тип данных и константу – статическую размерность. struct x {…}; FIFO a; FIFO b; FIFO c; Особенности разработки шаблонов структур данных Шаблон является исключительно средством подстановки, он ничего не меняет в ни в существе класса структуры данных, для которой строится шаблон, ни в принципах передачи объектов класса – параметров шаблона. Во-первых, это касается способа хранения объектов в структуре данных: она может содержать указатели, а может и сами объекты (копии, значения): · если шаблон хранит указатели на объекты, то он не касается проблем корректного копирования объектов и «не отвечает» за их создание и уничтожение. Деструктор шаблона обязан уничтожить динамические компоненты структуры данных (динамические массивы указателей, элементы списка), но он обычно не уничтожает хранимые объекты; · если шаблон хранит сами объекты, то он «должен быть уверен» в корректном копировании объектов при их записи и чтении из структуры данных (конструктор копирования о переопределение присваивания для объектов, содержащих динамические данные). При разрушении структуры данных разрушаются и копии хранимых в ней объектов. Во-вторых, шаблон может использовать ряд стандартных операций по отношению к типу данных – параметру шаблона: присваивание (копирование), сравнение, а также ввод и вывод в стандартные потоки. При использовании шаблона с параметром – не базовым типом, а классом, необходимо следить, чтобы эти операции были в нем переопределены. Шаблоны классов списков Для представления списка или дерева необходимы две сущности: элементы списка (вершины дерева), связанные между собой и заголовок – указатель на первый элемент списка (корневую вершину). В технологии ООП есть два равноправных решения: · разрабатывается один класс, объекты которого играют разную роль в процессе работы класса. Первый объект – заголовок, создается программой (статически или динамически), доступен извне и не содержит данных (по крайней мере, в момент конструирования). Остальные объекты, содержащие данные, создаются динамически методами, работающими с первым объектом. Этот вариант имеет некоторые тонкости, связанные с тем, что программа должна уметь различать, где она работает с элементом списка, а где с элементом-заголовком; · разрабатывается два класса – класс элементов списка и класс списка как такового, содержащего, как минимум, его заголовок. Объекты первого (вспомогательного) класса пользователем (программой, работающей с классом) не создаются. Они все – динамические, и их порождают методы второго (основного) класса; Ход работы Рассмотрим первый вариант на примере шаблона односвязного списка. Коллизий, связанных с распознаванием заголовочного элемента и элемента, содержащего данные, не возникает. Все методы, описанные в заголовке класса, применяются только по отношению к заголовочному элементу (в контексте все время фигурирует установка на первый элемент списка в виде p=next, либо установка на «предыдущий»-заголовочный в виде p=this). Часть простых методов реализована в самом заголовке класса, в них для указателей на элементы списка используется сокращенный контекст вида list *p, хотя класс list является шаблонным. //------------------------------------------------------105-04.cpp template class list{ list *next; // Указатель на следующий в списке
94 T data; // Элемент списка хранит сам объект list(T& v) { data=v; next=NULL;} // Скрытый конструктор для элементов с данными public: list() { next=NULL; } // Конструктор для элемента - заголовка list(){ // Деструктор рекурсивный if (next!=NULL) delete next; } // рекурсивное удаление следующего void front(T& v){ // Включение в начало list *q=new list(v); q->next=next; next=q; } void end(T &v){ // Включение в конец list *p,*q=new list(v); // Дойти до последнего for(p=this;p->nezt!=NULL;p=p->next); p->next=q; // Следующий за последним - новый } void insert(T&,int); // Включение по логическому номеру void insert(T&); // Включение с сохранением порядка T remove(int); // Извлечение по ЛН operator int(){ // Приведение к int = размер списка list *q; int n; for(q=next,n=0; q!=NULL; n++,q=q->next); return n; } friend ostream &operator<<(ostream&, list&); friend istream &operator>>(istream&, list&); }; // Переопределенный вывод в поток Единственная коллизия возникает в конструкторе и деструкторе. Для заголовочного элемента используется конструктор без параметров. Методы списка, создавая динамические элементы – объекты того же класса, используют закрытый конструктор с параметром – значением, хранимым в элементе списка. В методе удаления элемента из списка кроме логического исключения выбранного элемента из цепочки у него обнуляется указатель на следующего (p->next=NULL). Это делается для того, чтобы исключить рекурсивный вызов деструктора при удалении одного элемента списка. Специфика односвязного списка проявляется в реализации методов вставки по номеру, с сохранением порядка и удаления. Текущий указатель в цикле ссылается на предыдущий элемент списка по отношению к искомому (поэтому, например, используется выражение q->next- >data для сравнения значения в искомом элементе). //------------------------------------------------------105-04.cpp template void list::insert(T &newdata,int n){ list *p,*q; p=new list(newdata); for (q=this; q->next!=NULL && n!=0; n--,q=q->next); p->next=q-> next; // Вставка после текущего q->next=p; } // Отсчет от заголовка //---------------------------------------------------------------------------------------- template void list::insert(T &newdata){ list *p,*q; p=new list(newdata); // Сравнивать СО СЛЕДУЮЩИМ for (q=this; q->next!=NULL && newdata>q->next->data; q=q->next); p->next =q->next; // Вставка ПОСЛЕ текущего q->next=p;} //---------------------------------------------------------------------------------------- template T list::remove(int n){ list *q,*p; // Указатель на ПРЕДЫДУЩИЙ
95 for (q=this; q->next!=NULL && n!=0; n--,q=q->next); T val; if (q->next==NULL) return val; // Такого нет val=q->next->data; p=q->next; q->next=p->next; // Исключить СЛЕДУЮЩИЙ из цепочки p->next=NULL; // Для исключения рекурсивного деструктора delete p; return val;} Переопределенные операции ввода-вывода в стандартные потоки поддерживают саморазворачивающийся симметричный формат представления данных, использующий счетчик элементов. При вводе в соответствии с прочитанным значением счетчика многократно читается объект класса T, значение которого каждый раз включается в список. //------------------------------------------------------105-04.cpp template ostream &operator<<(ostream &O, list &R){ list *q; O << (int)R << endl; for (q=R.next; q!=NULL; q=q->next) O << q->data << endl; return O; } template istream &operator>>(ostream &I, list &R){ T val; int n; I >> n; while(n--!=0){ I >> val; R.front(val); } return I; } Практическая работа № 1.23. Использование порождающих шаблонов Цель работы: ознакомиться с порождающими шаблонами Теоретический материал Порождающие шаблоны Абстрактная фабрика — порождающий шаблон проектирования, позволяющий изменять поведение системы, варьируя создаваемыми объектами, при этом сохраняя интерфейсы. Он позволяет создавать целые группы взаимосвязанных объектов, которые, будучи созданными одной фабрикой, реализуют общее поведение. Шаблон реализуется созданием абстрактного класса Factory, который представляет собой интерфейс для создания компонентов системы (например, для оконного интерфейса он может создавать окна и кнопки). Затем пишутся классы, реализующие этот интерфейc. Этот шаблон предоставляет интерфейс для создания семейств взаимосвязанных или взаимозависимых объектов, не специфицируя их конкретных классов. Фабричный метод (Factory Method) Фабричный метод — порождающий шаблон проектирования, предоставляющий подклассам интерфейс для создания экземпляров некоторого класса. В момент создания наследники могут определить, какой класс создавать. Иными словами, Фабрика делегирует создание объектов наследникам родительского класса. Это позволяет использовать в коде программы не специфические классы, а манипулировать абстрактными объектами на более высоком уровне. Шаблон определяет интерфейс для создания объекта, но оставляет подклассам решение о том, какой класс инстанцировать. Фабричный метод позволяет классу делегировать создание подклассов. Используется, когда: ●классу заранее неизвестно, объекты каких подклассов ему нужно создавать. ●класс спроектирован так, чтобы объекты, которые он создаёт, специфицировались подклассами. ●класс делегирует свои обязанности одному из нескольких вспомогательных подклассов, и планируется локализовать знание о том, какой класс принимает эти обязанности на себя. Структура:
96 Product — продукт; определяет интерфейс объектов, создаваемых абстрактным методом. ConcreteProduct — конкретный продукт, реализует интерфейс Product. Creator — создатель; объявляет фабричный метод, который возвращает объект типа Product. Может также содержать реализацию этого метода «по умолчанию»; может вызывать фабричный метод для создания объекта типа Product. ConcreteCreator — конкретный создатель; переопределяет фабричный метод таким образом, чтобы он создавал и возвращал объект класса ConcreteProduct. Одиночка (Singleton) Одиночка — порождающий шаблон проектирования, гарантирующий, что в однопоточном приложении будет единственный экземпляр класса с глобальной точкой доступа. Существенно то, что можно пользоваться именно экземпляром класса, так как при этом во многих случаях становится доступной более широкая функциональность. Глобальный «одинокий» объект — именно объект, а не набор процедур, не привязанных ни к какому объекту — бывает нужен: ●если используется существующая объектноориентированная библиотека; ●если есть шансы, что один объект когданибудь превратится в несколько; ●если интерфейс объекта (например, игрового мира) слишком сложен, и не стоит засорять основное пространство имён большим количеством функций; ●если, в зависимости от какихнибудь условий и настроек, создаётся один из нескольких объектов. Например, в зависимости от того, ведётся лог или нет, создаётся или настоящий объект, пишущий в файл, или «заглушка», ничего не делающая. Поведенческие шаблоны Стратегия (Strategy) Стратегия — поведенческий шаблон проектирования, предназначенный для определения семейства алгоритмов, инкапсуляции каждого из них и обеспечения их взаимозаменяемости. Это позволяет выбирать алгоритм путем определения соответствующего класса. Шаблон Strategy позволяет менять выбранный алгоритм независимо от объектовклиентов, которые его используют. Проблема: по типу клиента (или по типу обрабатываемых данных) выбрать подходящий алгоритм, который следует применить. Если используется правило, которое не подвержено изменениям, нет необходимости обращаться к шаблону «стратегия». Решение: отделение процедуры выбора алгоритма от его реализации. Это позволяет сделать выбор на основании контекста. Класс Strategy определяет, как будут использоваться различные алгоритмы. Конкретные классы ConcreteStrategy реализуют эти различные алгоритмы. Класс Context использует конкретные классы ConcreteStrategy посредством ссылки на конкретный тип абстрактного класса Strategy. Классы Strategy и Context взаимодействуют с целью реализации выбранного алгоритма (в некоторых случаях классу Strategy требуется посылать запросы классу Context). Класс Context пересылает классу Strategy запрос, поступивший от его классаклиента. Наблюдатель (Observer) Наблюдатель — поведенческий шаблон проектирования. Создает механизм у класса, который позволяет получать экземпляру объекта этого класса оповещения от других объектов об изменении их состояния, тем самым наблюдая за ними. Определяет зависимость типа «один ко многим» между объектами таким образом, что при изменении состояния одного объекта все зависящие от него оповещаются об этом событии. При реализации шаблона «наблюдатель» обычно используются следующие классы: ●Observable — интерфейс, определяющий методы для добавления, удаления и оповещения наблюдателей; ●Observer — интерфейс, с помощью которого наблюдатель получает оповещение; ●ConcreteObservable — конкретный класс, который реализует интерфейс Observable; ●ConcreteObserver — конкретный класс, который реализует интерфейс Observer. Шаблон «наблюдатель» применяется в тех случаях, когда система обладает следующими свойствами: ●существует, как минимум, один объект, рассылающий сообщения;
97 ●имеется не менее одного получателя сообщений, причём их количество и состав могут изменяться во время работы приложения; ●нет надобности очень сильно связывать взаимодействующие объекты, что полезно для повторного использования. Данный шаблон часто применяют в ситуациях, в которых отправителя сообщений не интересует, что делают получатели с предоставленной им информацией. Команда (Command) Команда — поведенческий шаблон проектирования, используемый при объектноориентированном программировании, представляющий действие. Объект команды заключает в себе само действие и его параметры. Паттерн обеспечивает обработку команды в виде объекта, что позволяет сохранять её, передавать в качестве параметра методам, а также возвращать её в виде результата, как и любой другой объект. Паттерн Command преобразовывает запрос на выполнение действия в отдельный объекткоманду. Такая инкапсуляция позволяет передавать эти действия другим функциям и объектам в качестве параметра, приказывая им выполнить запрошенную операцию. Команда – это объект, поэтому над ней допустимы любые операции, что и над объектом. Интерфейс командного объекта определяется абстрактным базовым классом Command и в самом простом случае имеет единственный метод execute(). Производные классы определяют получателя запроса (указатель на объектполучатель) и необходимую для выполнения операцию (метод этого объекта). Метод execute() подклассов Command просто вызывает нужную операцию получателя. Впаттерне Command может быть до трех участников: ●Клиент, создающий экземпляр командного объекта. ●Инициатор запроса, использующий командный объект. ●Получатель запроса. Сначала клиент создает объект ConcreteCommand, конфигурируя его получателем запроса. Этот объект также доступен инициатору. Инициатор использует его при отправке запроса, вызывая метод execute(). Этот алгоритм напоминает работу функции обратного вызова в процедурном программировании – функция регистрируется, чтобы быть вызванной позднее. Паттерн Command отделяет объект, инициирующий операцию, от объекта, который знает, как ее выполнить. Единственное, что должен знать инициатор, это как отправить команду. Это придает системе гибкость: позволяет осуществлять динамическую замену команд, использовать сложные составные команды, осуществлять отмену операций.
Скачать 3.25 Mb.