Полиморфные структуры данных

Особый интерес представляет последний случай в определении полиморфизма -- полиморфная структура данных, называемая также полиморфным контейнером. Рассмотрим типичный контейнер -- список, предназначенный для хранения транспортных средств:



fleet: LIST [VEHICLE]

Рассмотрим вызов, такой как fleet.extend(...), добавляющий элемент в список. Какой вид аргументов можно использовать в вызове, заменяя "..."? Если посмотреть на объявление extend вLIST[G], то можно видеть:

extend (v: G)

-- Добавить новое вхождение v в конец.

В случае с fleet фактическим родовым параметром, соответствующим G, является тип VEHICLE, так что вызов ожидает аргумента типа VEHICLE, как в вызове: feet.end (myvehicle)

Но полиморфизм играет свою роль, и любой тип, являющийся потомком VEHICLE, может прекрасно использоваться. Поэтому наряду с возможностью применения myvehicle вполне корректно использовать вызов:

fleet.extend ( cab_at_corner)

В общем случае, аргумент может быть любого типа, являющегося потомком VEHICLE, таким как TAXI, TRAM и другие.

Полиморфный контейнер является результатом последовательности подобных вставок c возможностью различных фактических типов в каждом случае. После нескольких вызовов extend наш список fleet может выглядеть, например, так:

Рис. 1.6. Полиморфный список



Список содержит смесь объектов различных типов, все из них являются потомками VEHICLE (включая BUS, не появлявшийся ранее).

Возможность построения таких полиморфных структур данных -- результат комбинации двух фундаментальных ОО-механизмов, наследования и универсальности. Это дает нам новый уровень гибкости. Рассмотрим, например, запрос last, результатом которого будет последний элемент списка. Он объявлен в классе LIST[G] и возвращает результат типа G. Сущность fleet объявлена как fleet: LIST[ VEHICLE], используя VEHICLE в качестве фактического родового параметра для G. Поэтому выражение: fleet.last будет иметь тип VEHICLE. В каждом конкретном случае результирующий объект может быть объектом любого из потомков. Если список находится в состоянии, показанном на последнем рисунке, объектом будет TAXI, но это может быть и другой тип, и вы не знаете, какой именно. Но это и не нужно знать, поскольку к результату можно применять любую компоненту класса VEHICLE. После объявления v: VEHICLE и присвоения v:=fleet. last допустимы вызовы v.load(...) и v.count. Эти вызовы компонентов класса VEHICLE корректны, но, конечно же, нельзя вызывать компоненты классов потомков, например, v.take(...), так как take ожидает не просто VEHICLE аргумент, а TAXI.

Я могу услышать от вас: это несправедливо! Просто взгляните на последний рисунок, ведь последний объект -- такси. Почему же я не могу выполнить операцию, вполне допустимую для этого объекта?

Не горячитесь.

Во-первых, жизнь полна несправедливостей, и нужно уметь принимать ее такой, какой она есть.

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

И третье: все будет хорошо -- и это настоящий ответ! Существуют способы проверки того, чем является полученный объект, является ли он в самом деле такси в данном конкретном выполнении, и если да, то вызов take можно сделать законным. Но прежде чем узнать, как это делается, придется прочесть еще несколько десятков страниц. Разве я не говорил вам, что жизнь полна несправедливостей? В данный момент более важно понимание эффекта правильных вызовов -- вызовов компонентов VEHICLE, таких как v.load(...) и v.count для случая полиморфной цели. Ответ ведет нас к еще одной фундаментальной ОО-концепции.

Динамическое связывание

В вызове, таком как v.load(.), цель v является полиморфной, так что во время выполнения она может быть присоединена к объекту типа TAXI, или TRAM, или к любому потомку VEHICLE.

Если теперь вы посмотрите на текст этих классов, то увидите, что каждый из них имеет собственную реализацию метода load (ниже мы увидим, как создавать такие объявления без двусмысленностей и конфликтов). Какая же версия должна реально вызываться?

Единственно правильный ответ -- мы хотим вызывать правильный компонент. Правильный в том смысле, что он наиболее точно соответствует типу объекта, к которому присоединена сущность v в момент выполнения. Когда этот объект является экземпляром TAXI, мы хотим, чтобы вызывалась версия класса TAXI, когда TRAM -- то TRAM -версия, и так далее.

Рис. 1.7. Знакомое наследование



Любое другое решение было бы некорректным. Глупо было бы применять операцию посадки в трамвай при посадке в такси. Даже применять операцию по умолчанию, из класса VEHICLE, даже если она там предусмотрена, нецелесообразно. Понятно, что автор класса TAXI, который задал реализацию load, специально приспособленную для посадки в такси, был бы крайне удивлен, если бы использовалась для этих целей другая реализация, предназначенная для посадки в другое транспортное средство.

Объявление v: VEHICLE имеет целью сделать переменную v достаточно общей, чтобы при разных выполнениях она могла связываться с разными объектами -- иногда с такси, иногда с трамваем, с различными видами транспортных средств. Но в любом конкретном вызове она всегда обозначает не какой-то абстрактный объект -- она всегда присоединена к объекту конкретного типа. Компоненты, которые применяются к объекту, должны учитывать его специфику.

Эта политика, являясь краеугольным камнем конструирования ОО ПО, имеет собственное имя.

Определение: динамическое связывание

Динамическое связывание (семантическое правило) требует, чтобы при вызове компонента использовалась та версия компонента, которая наилучшим образом адаптирована к типу целевого объекта.

Противоположная позиция носит название статического связывания. Это может звучать удивительно, но статическое связывание применяется во многих языках. Прежде всего стоит упомянуть язык С++ и его потомков, где статическое связывание является политикой, используемой по умолчанию, и применить динамическое связывание возможно только по явному требованию, объявив соответствующий компонент (функцию или метод в С++) виртуальным ( virtual ).

Типизация и наследование

Как вы, вероятно, уже догадались, есть предел гибкости типизации, обеспечиваемой полиморфизмом. Все хорошо, когда переменная типа VEHICLE обозначает объект TAXI или TRAM, но было бы неправильно позволять ей присоединяться к объектам, представляющим пассажиров или город.

Правило прямолинейно: при полиморфном присоединении тип источника должен быть потомком типа цели. Это не вполне подходящая терминология, -- ниже мы увидим, как сделать ее корректной, -- но она выражает основную идею. Отсюда следует, что наш прежний пример присваивания my_vehicle:= cab_at_corner является корректным, а присваивание my_vehicle:= Paris -- недопустимо. Город Париж не является транспортным средством.

Это правило стоит за разнообразием возможностей, обсуждаемых ранее. Если мы допускаем присваивание x:= y, где x типа T, а y типа U, мы должны быть уверенными, что вызов x.f будет иметь смысл во время выполнения, не только если целевой объект типа T, но и в том случае, если он имеет тип U, при условии, что вызов признан корректным во время компиляции. Это условие корректности является обычным и основывается на объявлении x, оно устанавливает, что f должно быть компонентом T. Но нам нужны гарантии, что f также является компонентом U. Это выполняется по определению, если U потомок T.

Следующие термины помогают в понимании этих концепций.

Статический тип, динамический тип

Статическим типом сущности или выражения e является тип, используемый в объявлении в соответствующем тексте класса.

Если e во время конкретного выполнения присоединено к объекту, то тип этого объекта будет динамическим типомe.

После присваивания my_vehicle:= cab_at_corner сущность my_vehicle имеет динамический тип TAXI. Ее статический тип является типом, заданным в объявлении -- VEHICLE.

Эти понятия применимы к сущностям и выражениям. Для объектов такого различия типов нет. Для них определен только динамический тип, появляющийся в момент создания объекта, -- это типTAXI, или TRAM, или что-либо еще, но всегда остающийся неизменным конкретный тип объекта.

Следствием этого базисного правила для типов является утверждение, что любой динамический тип сущности или выражения должен быть согласован со статическим типом.

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

· TAXI (не имеет родовых параметров) согласовано c VEHICLE, так как является его потомком;

· LINKED_LIST[TAXI] согласовано с LIST[TAXI], так как LINKEDLIST является потомком LIST и фактический родовой параметр один и тот же.

Дадим более точное определение этого свойства.

Определение: согласование

Если класс D является потомком класса C и оба не развернутые, то типы, выводимые из D, согласованы с теми, что выводимы из C, следующим образом:

· если класс D не являются универсальным, то D (как тип) согласован с C ;

· если класс D является универсальным, то D[T, U,...] согласован с C[T, U,...] (с теми же самыми родовыми параметрами).

Развернутый тип согласован только с собой.

Полное определение допускает соответствие и в том случае, когда фактические родовые параметры не совпадают, но согласованы друг с другом. Так, LINKED_LIST[TAXI] согласован сLINKED_LIST[VEHICLE] (следовательно, и с LIST[VEHICLE] ), поскольку LINKEDLIST согласован с LIST, а класс TAXI согласован с VEHICLE. Этот случай требует особой внимательности, и нам он не нужен. Как обычно, когда возникает какая-либо неясность, следует обращаться к стандарту языка для полного понимания.

Все это нам понадобилось, чтобы дать корректную версию правила полиморфизма. Точное правило будет ссылаться на "согласование", а не на свойство "является потомком".

Правило полиморфизма типов

Чтобы полиморфное присоединение было правильным, тип источника должен быть согласован с типом цели.

Это подтверждает, что полиморфизм применим только к ссылочным типам, так как по определению развернутый тип согласован только с самим собой.

Правило типизации обеспечивает нам безопасность, гарантируя, что в фундаментальной операции ОО-программирования x..f (...) всегда будет компонент f, применимый к объекту, к которому присоединен x во время выполнения, даже если его тип может быть результатом полиморфного присоединения к x.

Интересно отметить комбинацию свойств, которые характерны для большинства современных ОО языков программирования.

· Статическая типизация, гарантирующая, что существует по меньшей мере один компонент для f.

· Динамическое связывание, гарантирующее использование лучшего компонента -- того, что непосредственно подходит типу объекта, если доступно более одного варианта реализации f.

Язык Smalltalk выбирает из этой политики комбинацию динамического связывания и динамической проверки типов. Как результат, неверное применение вызова компонента, например, Paris. load(.) (компонент класса VEHICLE применяется к цели класса CITY), не будет обнаружено на этапе трансляции, и ошибка проявится только во время выполнения, приводя к аварийному завершению программы. Цель такого подхода в том, чтобы избежать излишних проверок в период компиляции и обеспечить большую гибкость.

3. Паттерн Decorator

Component для промежуточной формы представления программы SSA (Single Static Assignment). Листовые подкласс^ RegisterTransf er определяют различные статические присваивания, например:

· примитивные присваивания, которые выполняют операцию над двумя регистрами и сохраняют результат в третьем;

· присваивание, у которого есть исходный, но нет целевого регистра. Следовательно, регистр используется после возврата из процедуры;

· присваивание, у которого есть целевой, но нет исходного регистра. Это означает, что присваивание регистру происходит перед началом процедуры.

Подкласс RegisterTransf erSet является примером класса Composite для представления присваиваний, изменяющих сразу несколько регистров.

Другой пример применения паттерна компоновщик - финансовые программы, когда инвестиционный портфель состоит их нескольких отдельных активов.

Можно поддержать сложные агрегаты активов, ?сли реализовать портфель в виде компоновщика, согласованного с интерфейсом каждого актива [ВЕ93].

Паттерн команда описывает, как можно компоновать и упорядочивать объекты Command с помощью класса компоновщика MacroCommand.

Родственные паттерны

Отношение компонент-родитель используется в паттерне цепочка обязанностей.

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

Паттерн приспособленец позволяет разделять компоненты, но ссылаться на своих родителей они уже не могут. Итератор можно использовать для обхода составных объектов.

Посетитель локализует операции и поведение, которые в противном случае пришлось бы распределять между классами Composite и Leaf.

Декоратор - паттерн, структурирующий объекты.

Назначение

Динамически добавляет объекту новые обязанности. Является гибкой альтернативой порождению подклассов с целью расширения функциональности.

Структурные паттерны

Мотивация

Иногда бывает нужно возложить дополнительные обязанности на отдельный объект, а не на класс в целом. Так, библиотека для построения графических интерфейсов пользователя должна ?уметь? добавлять новое свойство, скажем, рамку или новое поведение (например, возможность прокрутки к любому элементу интерфейса).

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

Более гибким является другой подход: поместить компонент в другой объект, называемый декоратором, который как раз и добавляет рамку. Декоратор следует интерфейсу декорируемого объекта, поэтому его присутствие прозрачно для клиентов компонента. Декоратор переадресует запросы внутреннему компоненту, но может выполнять и дополнительные действия (например, рисовать рамку) до или после переадресации. Поскольку декораторы прозрачны, они могут вкладываться друг в друга, добавляя тем самым любое число новых обязанностей.

Предположим, что имеется объект класса Text View, который отображает текст в окне. По умолчанию Text View не имеет полос прокрутки, поскольку они не всегда нужны. Но при необходимости их удастся добавить с помощью декоратора ScrollDecorator. Допустим, что еще мы хотим добавить жирную сплошную рамку вокруг объекта TextView. Здесь может помочь декоратор BorderDecorat or. Мы просто компонуем оба декоратора с BorderDecorator и получаем искомый результат.

Ниже на диаграмме показано, как композиция объекта TextView с объектами BorderDecorator и ScrollDecorator порождает элемент для ввода текста, окруженный рамкой и снабженный полосой прокрутки.

Классы ScrollDecorator и BorderDecorator являются подклассами Decorator - абстрактного класса, который представляет визуальные компоненты, применяемые для оформления других визуальных компонентов.

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

Подклассы Decorator могут добавлять любые операции для обеспечения необходимой функциональности. Так, операция ScrollTo объекта ScrollDecorator позволяет другим объектам выполнять прокрутку, если им известно о присут ствии объекта ScrollDecorator. Важная особенность этого паттерна состоит в том, что декораторы могут употребляться везде, где возможно появление самого объекта VisualComponent. Поэтому клиент не может отличить декорированный объект от недекорированного, а значит, и никоим образом не зависит от наличия или отсутствия оформлений.

Используйте паттерн декоратор:

· для динамического, прозрачного для клиентов добавления обязанностей объектам;

· для реализации обязанностей, которые могут быть сняты с объекта;

· когда расширение путем порождения подклассов по каким-то причинам неудобно или невозможно. Иногда приходится реализовывать много независимых расширений, так что порождение подклассов для поддержки всех возможных комбинаций приведет к комбинаторному росту их числа. В других случаях определение класса может быть скрыто или почему-либо еще недоступно, так что породить от него подкласс нельзя.

4. Паттерн визитер

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

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

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

Пользователь объект получает указатель на другой объект, который реализует алгоритм. Первый назван "элементом класса", а второй "посетителя класса". Идея состоит в использовании структуры элементов классов, каждый из которых имеет accept () метод, принимающий посетителей объекта аргумент. посетителей является протокол ( интерфейс в Java и C #) с визитом () методом определено, что каждый элемент класса может вызвать. Accept () метод класса элемента перезванивает визита () метод, который определяется в реализации посетителя. Отдельный конкретный посетитель классы могут быть записаны для выполнения той или иной операции, осуществление этих операций в своих визита () методов.

Один из них визита () методы конкретного посетителя можно рассматривать как метод не из одного класса, а метод пару классов: конкретный посетитель и определенного класса элемента. Таким образом, посетитель модель имитирует двойной диспетчеризации в обычной одно-отправка объектно-ориентированных языков, таких как Java , Smalltalk и C + + . Для объяснения того, как двойной диспетчеризации отличается от функции перегрузкисм. двойной диспетчеризации более перегрузку функции в двойном статья отправки. На языке Java, две технологии были документально подтверждено, что использование отражения для упрощения механики двойного моделирования отправки в посетителя шаблону. Начиная с JDK 1.2, необходимость "accept ()" методом было устранено путем добавления "GetMethod ()", который позволяет объекту, чтобы получить другую объектов методами с конкретными параметрами. "Invoke ()" Метод позволяет эти методы можно назвать. Несмотря на преимущество, используя отражающую посетитель дает код упрощение синтаксиса следует отметить, что отражающие картину посетитель может не подходить для перебора большого количества посещаемых объектов - есть значительные накладные расходы в размере от двух до пятидесяти раз в отражающей вызова метода по сравнению с обычными вызова метода ^{[ 1 ]} .

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

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

5. Паттерн Наблюдатель

Наблюдатель, Observer -- поведенческий шаблон проектирования. Также известен как "подчинённые" (Dependents), "издатель-подписчик" (Publisher-Subscriber). Реализация



При реализации шаблона "наблюдатель" обычно используются следующие классы.

§ Observable -- интерфейс, определяющий методы для добавления, удаления и оповещения наблюдателей.

§ Observer -- интерфейс, с помощью которого наблюдатель получает оповещение.

§ ConcreteObservable -- конкретный класс, который реализует интерфейс Observable.

§ ConcreteObserver -- конкретный класс, который реализует интерфейс Observer.

Шаблон "наблюдатель" применяется в тех случаях, когда система обладает следующими свойствами:

§ существует, как минимум, один объект, рассылающий сообщения

§ имеется не менее одного получателя сообщений, причём их количество и состав могут изменяться во время работы приложения.

§ нет надобности очень сильно связывать взаимодействующие объекты, что полезно для повторного использования.



6. Двусвязные списки

Двусвязные списки

Двусвязный список состоит из элементов данных, каждый из которых содержит ссылки как на следующий, так и на предыдущий элементы. На рис. 22.5 показана организация ссылок в двусвязном списке.

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

При вставке нового элемента в двусвязный список могут быть три случая: элемент вставляется в начало, в середину и в конец списка. Эти операции показаны на рис. 22.6.



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

struct address {

char name[40];

char street[40] ;

char city[20];

char state[3];

char zip[11];

struct address *next;

struct address *prior;

} info;

Следующая функция, dlstore(), создает двусвязный список, используя структуру address в качестве базового типа данных:

void dlstore(struct address *i, struct address **last)

{

if(!*last) *last = i; /* вставка первого элемента */

else (*last)->next = i;

i->next = NULL;

i->prior = *last;

*last = i;

}

Функция dlstore() помещает новые записи в конец списка. В качестве параметров ей необходимо передавать указатель на сохраняемые данные; а также указатель на конец списка, который при первом вызове должен быть равен нулю (NULL).

Подобно односвязным, двусвязные списки можно создавать с помощью функции, которая будет помещать элементы в определенные позиции, а не только в конец списка. Показанная ниже функция dls_store() создает список, упорядочивая его по возрастанию имен:

/* Создание упорядоченного двусвязного списка. */

void dls_store(

struct address *i, /* новый элемент */

struct address **start, /* первый элемент в списке */

struct address **last /* последний элемент в списке */

)

{

struct address *old, *p;

if(*last==NULL) { /* первый элемент в списке */

i->next = NULL;

i->prior = NULL;

*last = i;

*start = i;

return;

}

p = *start; /* начать с начала списка */

old = NULL;

while(p) {

if(strcmp(p->name, i->name)<0){

old = p;

p = p->next;

}

else {

if(p->prior) {

p->prior->next = i;

i->next = p;

i->prior = p->prior;

p->prior = i;

return;

}

i->next = p; /* новый первый элемент */

i->prior = NULL;

p->prior = i;

*start = i;

return;

}

}

old->next = i; /* вставка в конец */

i->next = NULL;

i->prior = old;

*last = i;

}

Поскольку первый и последний элементы списка могут меняться, функция dls_store() автоматически обновляет указатели на начало и конец списка посредством параметров start и last. При вызове функции необходимо передавать указатель на сохраняемые данные и указатели на указатели на первый и последний элементы списка. В первый раз параметры start и last должны быть равны нулю (NULL). Как и в односвязных списках, для получения элемента данных двусвязного списка необходимо переходить по ссылкам до тех пор, пока не будет найден искомый элемент. При удалении элемента двусвязного списка могут возникнуть три случая: удаление первого элемента, удаление элемента из середины и удаление последнего элемента. На рис. 22.7 показано, как при этом изменяются ссылки. Показанная ниже функция dldelete() удаляет элемент двусвязного списка:

void dldelete(

struct address *i, /* удаляемый элемент */

struct address **start, /* первый элемент */

struct address **last) /* последний элемент */

{

if(i->prior) i->prior->next = i->next;

else { /* new first item */

*start = i->next;

if(start) start->prior = NULL;

}

if(i->next) i->next->prior = i->prior;

else /* удаление последнего элемента */

*last = i->prior;

}

Поскольку первый или последний элементы списка могут быть удалены, функция dldelete() автоматически обновляет указатели на начало и конец списка посредством параметров start и last. При вызове ей передаются указатель на удаляемый элемент и указатели на указатели на начало и конец списка.

Рис. 22.7. Удаление элемента двусвязного списка

Размещено на Allbest.ru