Объектно-ориентированное программирование. Объектно-ориентированное программирование в действии. Объектноориентированное программирование
 Скачать 5.29 Mb.
|
|
Глава 15: Учебный пример: контейнерные классы Почти все нетривиальные компьютерные программы базируются на простых структурах данных, таких как связные списки, стеки, очереди, деревья, множества, словари. Поскольку эти структуры являются типичными, хорошо было бы иметь их в качестве многократно используемых компонентов. На самом деле можно создать такие компоненты, но возникающие при этом сложности часто очень значительны. Поэтому разработка многократно используемых контейнерных классов является хорошим учебным примером. Он иллюстрирует, как свойства языка программирования влияют на стиль разработки, а также демонстрирует некоторые достоинства и ограничения объектно- ориентированных методов. Далее мы рассмотрим три тесно связанных вопроса: • Можно ли сконструировать многократно используемую абстракцию контейнера данных общего назначения, которая не зависит от типа хранимых элементов и тем самым переносима из одного проекта в другой? PDF created with pdfFactory Pro trial version www.pdffactory.com • Должен ли такой контейнер содержать данные только одного типа (так называемые однородные контейнеры) или удастся построить контейнер, содержащий значения различного типа (разнородные контейнеры)? • Можно ли разрешить пользователю контейнера данных доступ к хранимым в нем элементам, гарантируя при этом защиту от удаления и маскировку внутренней реализации контейнера? 15.1. Использование традиционных подходов Чтобы увидеть проблему в перспективе, мы должны сперва рассмотреть, как структуры данных обычно реализуются в традиционных языках программирования (скажем, C и Pascal). Используем связный список целых чисел как пример моделируемой абстракции. В языке Pascal связный список образуется из записей двух типов. Первый тип — это начало списка, который содержит указатель на первый элемент: type List = record firstLink : Link; end; Начало (голова) списка может быть размещено статически, поскольку размер требуемой памяти (а именно единственный указатель) остается постоянным во время выполнения. Второй тип записей используется, чтобы хранить сами значения. Каждый узел Link содержит одно целое число и указатель на следующий элемент списка: type Link = record value : integer; nextElement : Link; end; Элементы должны размещаться и удаляться динамически, хотя такие подробности следует спрятать от пользователя. Это достигается с помощью разработки функций, которые добавляют значение в начало списка, возвращают первый элемент списка, удаляют его и т. д. procedure addToList(var aList : List, newVal : integer); (* добавляет новый элемент в список *) var newLink : Link; begin (* создать и проинициализировать новый элемент *) new(newLink); newLink.value := newVal; (* поместить его в начало списка *) newLink.nextElement := aList.firstLink; aList.firstLink := newLink; end; function firstElement (var aList : List) : integer; (* удаляет из списка и возвращает первый элемент *) var firstNode : Link; begin firstNode := aList.firstLink; firstElement := firstNode^.value; aList.firstLink := firstNode^.nextElement; dispose(firstNode); end; PDF created with pdfFactory Pro trial version www.pdffactory.com Главное здесь не детали реализации связного списка (их можно найти в любом учебнике по структурам данных), но возможности многократного использования. Предположим, что программист реализовал абстракцию связного списка, приведенную выше. Теперь он хочет использовать наряду со связным списком целых чисел связный список вещественных чисел. Проблема состоит в том, что язык программирования слишком строго проверяет типы данных. Тип integer, используемый для значения хранимого в списке, является неотъемлемой составной частью описания. Единственный способ ввести новый тип данных — это создать совершенно новую структуру RealLink, новую структуру начала списка RealList и подпрограммы для доступа к этим структурам данных. Нечто вроде записей с вариантными полями (тип данных union в языке C) может помочь использовать одну и ту же абстракцию списка для хранения как целых, так и вещественных чисел. В действительности вариантные записи позволяют определить разнородный список, который содержит и целые числа, и числа с плавающей точкой. Но вариантные записи — это только часть решения проблемы. Нельзя определить функцию, которая возвращает вариантную запись, так что по-прежнему требуется создавать отдельные функции для получения первого элемента списка. Более того, вариантная запись имеет только конечный набор допустимых альтернативных вариантов. Что если для следующего проекта потребуется совершенно новый тип списка (например, с текстовыми строками)? Теперь рассмотрим проблему доступа к произвольному элементу без удаления предшествующих ему элементов из контейнера. Типичный цикл, который печатает значения из списка, выглядит примерно так: var aList : List; (* обрабатываемый список *) p : Link; (* указатель, используемый в цикле *) begin p := aList.firstLink; while (p <> nil) do begin writeln(p.value); p := p.nextElement; end; Заметьте, что для прохождения цикла необходимо было ввести дополнительную переменную, названную здесь p. Она должна принадлежать типу данных Link, который мы намеревались замаскировать. Точно так же сам цикл требует доступа к полям переменной Link, которые мы также не хотели бы открывать. Итак, как мы видим, в традиционных языках программирования с контролем типов нет средств, необходимых для создания и обработки контейнеров, которые были бы истинно многократно используемыми. 15.2. Контейнеры в динамических языках Создание многократно используемых абстракций контейнеров происходит намного проще в языках программирования с динамическими типами данных (Smalltalk, Objective-C). На самом деле такие языки обычно уже содержат большой набор готовых абстракций PDF created with pdfFactory Pro trial version www.pdffactory.com данных, тем самым освобождая программиста от необходимости создавать контейнеры. Как мы видели выше при обсуждении вопроса о времени связывания, в языках программирования с динамическими типами данных знание о типе хранит в себе значение, а не переменная, с помощью которой осуществляется доступ к значению. Например, наша абстракция связного списка может быть определена через следующие структуры языка Objective-C: @ interface List : Object { id firstLink; } - (void) addToList : value - id firstElement @ end @ interface Link : Object { id Value id NextElement } + - id value - id nextElement @ end О значении, помещаемом в такую структуру, известно, что оно типа id (то есть типа данных «объект»). Аналогично значение, извлекаемое из списка, тоже типа id, но оно может быть присвоено любой объектной переменной, поскольку таким переменным разрешается хранить объект произвольного типа. Чтобы создать новый список, программист посылает сообщение new фабрике объектов в классе List: id aList aList = [ List new ]; Чтобы поместить значение в список, программист использует соответствующую функцию-член: [ aList addToList: aValue ]; Операции со списком не требуют никаких дополнительных знаний о типе значений, которые содержатся в списке, за исключением того, что это объекты: @ implementation List - (void) addList: newElement /* добавить в список новый элемент */ { id newLink; newLink = [ Link new ]; [ newLink setValue: newElement link: firstLink ]; firstLink = newLink; } - id firstElement /* удалить и вернуть первый элемент списка */ { id result; result = [ firstLink value ]; PDF created with pdfFactory Pro trial version www.pdffactory.com firstLink = [firstLink nextElement ]; return result; } @ end Аналогичным образом в языках программирования с динамическими типами данных можно обрабатывать итерации без того, чтобы выставлять на обозрение внутреннюю структуру контейнеров. Мы опишем две такие техники: одна используется в Smalltalk, а другая повсеместно применяется в разнообразных языках программирования. Мы отметили ранее, что в языке Smalltalk операторы могут быть сгруппированы в конструкцию, называемую block. Она во многом аналогична функции. Подобно функции, блок может иметь список аргументов. Стандартный способ выполнения итерации в языке Smalltalk — это передать блок как аргумент вместе с сообщением структуре, к которой осуществляется доступ. Цикл, который печатает значения списка, может быть записан следующим образом: aList do: [ :ele Ѕ ele print ] Класс списка просто пересылает блок классу элемента. Каждый элемент вызывает блок с использованием своего текущего значения, и затем пересылает блок следующему элементу. linkDo: aBlock " выполнить блок, передать его следующему элементу списка " aBlock value: value. nextLink notNil ifTrue: [ nextLink linkDo: aBlock ] При таком подходе удается производить разнообразные итерации, причем все — без показа структуры списка. В языке Objective-C и других объектно-ориентированных языках решение задачи об итерациях будет немного более сложным из-за отсутствия блоков. Листинг 15.1. Итератор в языке Objective-C @ implementation ListIterator { currentLink : id; } + newIterator : aList { self = [ ListIterator new ]; currentLink = [ aList firstLink ]; return self; } - id value { return [ currentLink value ] } - int atEnd { return currentLink == nil; } - void advance { if (! [ self atEnd ] ) PDF created with pdfFactory Pro trial version www.pdffactory.com currentLink = [ currentLink nextElement ]; } @end Стандартной альтернативой является создание вспомогательного объекта, называемого итератором (iterator). Этот объект поставляется разработчиком контейнерного класса (например, связного списка). Единственное назначение такого объекта — обеспечить доступ к элементам контейнера (один элемент за одно обращение) без показа внутренней структуры списка. Обычно итератор содержит указатель, с которым производятся всевозможные манипуляции. Листинг 15.1 иллюстрирует, как можно определить итератор для абстракции связного списка. Итератор обычно определяется самим списком как реакция на сообщение. Поэлементный цикл производится следующим образом: id aList; /* объявление списка */ id itr; /* объявление итератора */ for (itr = [ aList iterator ]; ! [ itr atEnd ]; [itr advance ]) print( [ itr value ] ); Заметьте, что хотя цикл потребовал объявления дополнительной переменной-итератора, ее использование не подразумевает знание внутренней структуры связного списка. Легкость, с которой конструируются и обрабатываются абстракции данных, — это один из основных рекламных лозунгов языков с динамическими типами. Контейнеры имеют совершенно общий вид и могут даже содержать разнородные наборы данных различных типов. К сожалению, такой выигрыш дается недаром. Как мы отметили ранее, существует дилемма между легкостью в использовании и эффективностью выполнения. Программы на динамических языках редко выполняются столь же эффективно, как в языках с более строгим контролем типов. 15.3. Контейнеры в языках со строгим контролем типа данных Мы переходим теперь к рассмотрению того, как контейнерные классы конструируются в языках со строгим контролем типа данных (Object Pascal, C++). Есть мнение, что принцип подстановки сам по себе обеспечивает решение проблемы контейнерных классов в таких языках. Согласно главе 6 принцип подстановки утверждает, что переменной, которая объявлена с определенным типом, можно на самом деле присвоить значение подтипа. Принцип подстановки на самом деле до некоторой степени облегчает решение наших проблем, но далеко не всех. Чтобы использовать подстановку, мы прежде всего должны создать класс, который бы был родителем всего, что мы захотим хранить в нашей структуре данных. Назовем этот гипотетический класс ListElement. Затем создадим абстракцию списков с элементами. Листинг 15.2 показывает, как это можно сделать в Object Pascal. Объекты, хранящиеся в списке, должны быть описаны как подклассы класса ListElement. Соответственно мы не можем построить список с целыми или вещественными числами, пока не породим эти типы данных из класса ListElement. Обычно это не очень серьезная проблема. На самом деле мы получили разнородный список со значениями различного типа, если только все они являются подклассами базового класса ListElement. PDF created with pdfFactory Pro trial version www.pdffactory.com Настоящая проблема возникает, когда мы хотим сделать что-либо с элементом, извлеченным из списка. Контроль типов данных, который определяет результат как принадлежащий классу ListElement, встает на нашем пути. Мы должны «отменить» подстановку дочернего типа данных вместо родительского типа. Предположим, к примеру, что мы создали два подкласса для класса ListElement. Подкласс WhiteBall представляет белые шары, а подкласс BlackBall — черные. Мы имеем список шаров и хотим извлечь первый элемент списка, присвоив его значение переменной типа WhiteBall. Листинг 15.2. Описание контейнерного класса на языке Object Pascal type List = object firstLink : ListElement; procedure addToList(var newValue : ListElement); function firstValue : ListElement; end; ListElement = object next : ListElement; end; procedure List.addToList(var newValue : ListElement); (* добавляет значение к началу списка *) begin (* поле связи должно указывать на текущий элемент *) newValue.next := firstLink; (* изменить ссылку в первом элементе списка *) firstLink := newValue; end; function firstValue : ListElement; (* исключить из списка первый элемент и вернуть его *) var first : ListElement; begin first := firstLink; firstValue := firstLink; firstLink := first.next; end; Мы говорили при обсуждении связывания, что здесь на самом деле имеются два момента, которые, однако, в некоторых объектно-ориентированных языках соединены: • Можем ли мы определить тип значения, полученного из списка? • Если да, то позволит ли компилятор выполнить присваивание безопасно с точки зрения сохранения типа? Вспомним, что в Object Pascal первая из двух проблем решается через использование логической функции Member, которая говорит нам, содержит ли переменная значение, относящееся к заданному классу. Если функция Member показывает, что преобразование является законным, то может быть задействовано приведение типа для преобразования значения к соответствующему типу данных: var aBall : WhiteBall; aList : List; aValue : ListElement; (* извлечь элемент из списка *) aValue := aList.firstElement; (* тип данных соответствует? *) PDF created with pdfFactory Pro trial version www.pdffactory.com if Member(aValue, WhiteBall) then (* присваивание законно *) aBall := WhiteBall(aValue); То есть извлечение элемента из структуры данных может выполняться в несколько этапов, но это именно та техника, которая используется во многих коммерчески доступных структурных классах. Сложность в использовании этих структур привела программистов к необходимости рассмотреть альтернативные варианты. Циклы часто создаются через структуры, подобные итераторам (см. приведенное выше решение этой проблемы в языке Objective-C). Однако, как и в случае функции firstElement, результатом работы итератора может быть только значение типа ListElement. Обязанностью программиста является привести его к другому типу данных: var aList : List; aValue : ListElement; itr : ListIterator; itr := aList.iterator; while (not itr.atEnd) do begin aValue := itr.current; if Member(aValue, WhiteBall) then itr.advance; (* следующее значение итератора *) end; До того как была введена система RTTI (Run-Time Typing Information — идентификация типа во время выполнения), в языке C++ значения обычно не знали своего собственного динамического типа. Это усложняло построение контейнеров, поскольку программист должен был не только приводить тип, но и обеспечивать собственный механизм определения динамического типа значений. Недавнее появление функции dynamic_cast призвано решить именно эту проблему. 15.4. Скрытое приведение типа данных при наследовании Принципиальные сложности в использовании техники, описанной в предыдущем разделе, состоят в следующем: • Структура данных может хранить только те значения, которые относятся к подклассу класса ListElement. • Язык программирования должен поддерживать принцип подстановки. • Объекты обязаны знать свой собственный динамический тип. • При извлечении данных требуется как явная проверка типа, так и операция приведения типа. Приведение типа — это довольно опасная конструкция, которую при программировании следует избегать где только возможно. Вдобавок при создании абстракций данных в C++ существенной становится вторая трудность. Вспомним, что C++ не поддерживает подстановку для объектов, объявленных обычным образом (поддержка осуществляется только для указателей и ссылок). По этой причине многие структуры данных в языке C++ разработаны так, чтобы хранить указатели на значения, а не сами значения. PDF created with pdfFactory Pro trial version www.pdffactory.com Стандартно предлагаемая техника программирования использует дочерние классы и наследование, чтобы замаскировать необходимость приведения типа в такой ситуации. Предположим, например, что мы уже имеем абстракцию данных со следующим интерфейсом: class GenericList // список указателей общего вида void * { public: void addToList (void * newElement); void * firstElement(); private: GenericLink * firstLink; }; class GenericLink { public: void * value; GenericLink * nextLink; }; Соответственно наш список общего вида содержит указатели void. Они могут указывать на что угодно. В теории такая совокупность может быть сколь угодно разнородной при использовании указателей на объекты различного типа. Теперь предположим, что мы хотим создать список указателей на окна (структура Window). Единственное, что надо сделать, — это определить подкласс класса общего вида и изменить типы аргументов и результата в методах, возвращающих элемент списка. В любом случае фактическую работу выполняет родительский класс. class WindowList : public GenericList { public: void addToList (Window * newElement) { GenericList::addToList (newElement); } Window * firstElement () { return (Window *) GenericList::firstElement; } }; Таким способом удается создать структуры данных, которые хранят значения, отличные от указателей (целые и вещественные числа). Но реализация требует определения подклассов как для класса List, так и для класса Link, а также, вероятно, создания новых классов-итераторов. Мы достигли до некоторой степени многократного использования кода, но только за счет того, что заставили программиста вводить новые подклассы всякий раз, когда он хочет применить абстракцию данных. Многие программисты отвергают такое решение просто потому, что оно доставляет не меньше хлопот, чем написание структур данных «с нуля». 15.5. Параметризованные классы Последний наш тезис состоял в том, что (по крайней мере для языков со строгим контролем типа данных) само по себе наследование недостаточно для создания простых в использовании контейнерных классов. Должен применяться другой механизм. Такой механизм существует. Он заключается в определении класса с типом в качестве PDF created with pdfFactory Pro trial version www.pdffactory.com параметра. Такие классы называются шаблонами в C++ и обобщенными классами в некоторых других языках. Шаблоны дают программисту возможность определять типы данных, в которых информация о типе преднамеренно остается незаданной. Этот пробел заполняется позднее. Чтобы лучше понять параметризацию, представьте себе, что описанию класса тип поставляется как аргумент процедуры или функции. Точно так же, как при вызове функции ей могут передаваться различные значения через список аргументов, так и разные «воплощения» параметризованного класса получают информацию о типе- параметре. Параметризованное описание класса для абстракции связного списка записывается в C++ следующим образом: template class List { public: void addElement (T newValue); T firstElement (); ListIterator iterator(); private: Link * firstLink; }; template class Link { public: T value; Link * nextLink; Link(T, Link *); }; Внутри шаблона класса аргумент шаблона (в данном случае идентификатор T) может использоваться как имя типа данных. Соответственно, разрешается определять переменные типа T, вводить функции, возвращающие результат типа T, и т. д. Функции-члены, которые определяют методы в шаблоне класса, должны также описываться как шаблоны: template void List::addElement(T newValue) { firstLink = Link new (newValue, firstLink); } template T List::firstElement() { Link first = firstLink; T result = first.value; firstLink = first->nextLink; delete first; return result; }; template Link::Link(T v, Link * n) : value(v); nextLink(n) { } PDF created with pdfFactory Pro trial version www.pdffactory.com Пользователь создает различные виды списков, указывая конкретные типы. Например, следующие операторы определяют списки целых и вещественных чисел: List listOne; List listTwo; Таким способом могут быть созданы только однородные списки. Шаблоны — элегантное решение проблемы контейнерных классов. Они позволяют достичь истинного многократного использования, создавать и обрабатывать компоненты общего назначения с минимумом сложностей, а также гарантировать безопасность при обращении с типами, что является целью языков программирования со строгим контролем типов данных. Недостатки имеются и у шаблонов. Они не позволяют определять списки разнородных данных, поскольку все элементы должны соответствовать объявленному типу. (Эту проблему можно обойти за счет хранения указателей на значения вместо самих значений.) Более важный недостаток: реализация шаблонов сильно варьируется в отношении как легкости использования, так и качества получаемого кода в различных компиляторах. Большинство из них не делают ничего, кроме интерпретации шаблонов в виде сложных макросов, так что для каждого нового параметра-типа создается совершенно новое определение класса и полностью независимые тела методов. Не нужно говорить, что это приводит к значительному увеличению размера кода. Тем не менее, поскольку шаблоны освобождают программиста от большого количества нудной работы (а именно от переписывания классов для новых структур данных в очередном приложении), они пользуются большой популярностью. В следующей главе мы рассмотрим библиотеку шаблонов. 15.5.1. Циклы и итерации в C++ Существование механизма шаблонов как для классов, так и для индивидуальных функций позволяет определить не один, а два различных способа итераций в C++. Оба они включены в недавно разработанную стандартную библиотеку шаблонов для C++, которая рассматривается в главе 16. Первый способ использует итератор. Контейнерный класс определяет тип данных для итератора, а также функции, которые возвращают значение итератора. Например, итератор для нашего класса связных списков записывается следующим образом: template class List { public: typedef ListIterator iterator; iterator begin() { // верни мне итератор в исходном состоянии return ListIterator (firstLink); } iterator end() { // конец return ListIterator (0); PDF created with pdfFactory Pro trial version www.pdffactory.com } } template class ListIterator { public: ListIterator (Link * sl) : currentLink(sl) { } void operator ++ () { // переход к следующему элементу currentLink = currentLink->nextLink; } T operator * () { // вернуть текущий элемент return currentLink->value; } bool operator == (ListIterator & right) { return currentLink == right.currentLink; } private: Link * currentLink; }; Теперь итератор может быть объявлен и инициализирован заданным списком. Поэлементный цикл выполняется без знания внутренней структуры списка: List::iterator start = aList.begin(); List::iterator end = aList.end(); for (; itr != end; itr++) { cout << (*itr) << endl; }; Второй вид итераций, называемый иногда итерациями с применением, в некотором отношении похож на циклы в языке Smalltalk. При такой итерации контейнер получает функцию в качестве аргумента, и он сам применяет ее к каждому элементу совокупности. Эти два действия объединяются в функции for_each, которая применяет передаваемую как аргумент функцию к каждому элементу списка: void printOut(int n) { cout << "the collection contains a " << n << "\n"; } for_each (aList.begin(), aList.end(), printOut); Проблема с итерациями такого типа состоит в том, что они требуют создания или использования функции, передаваемой в качестве аргумента. Если контейнер является чисто локальным объектом, такую функцию зачастую довольно сложно определить. В таких ситуациях цикл с использованием итератора может быть проще. Упражнения 1. Контейнерные классы в объектно-ориентированном программировании: успех или неудача? PDF created with pdfFactory Pro trial version www.pdffactory.com 2. Структуры данных разделяются на те, которые характеризуются своей реализацией (связные списки, деревья), и на те, которые определяются их предназначением (стеки, множества). Опишите, как можно использовать ООП для упрощения второго типа структур и маскировки деталей их реализации. Приведите в качестве иллюстрации структуру данных с единым интерфейсом и двумя радикально отличающимися реализациями. 3. Дайте пример разнородного контейнера, то есть контейнера значений различного типа. 4. Подход Smalltalk к построению итераций состоит в том, чтобы сгруппировать операции, которые надо выполнить, в блок и передать его структуре данных. Напротив, итератор — это структура, которая передает данные одно за другим внешней процедуре, где с ними выполняются нужные действия. Можно ли реализовать подход Smalltalk в других языках программирования (Object Pascal, C++)? Как при этом сказывается строгий контроль типов? 5. Приведите пример шаблонов, не связанных с контейнерными классами. |