Глава     15

Учебный пример: контейнерные классы

Разделы

Содержание

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

Далее мы рассмотрим три тесно связанных вопроса:

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;

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

Проблема состоит в том, что язык программирования слишком строго проверяет типы данных. Тип 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). На самом деле такие языки обычно уже содержат большой набор готовых абстракций данных, тем самым освобождая программиста от необходимости создавать контейнеры. Как мы видели выше при обсуждении вопроса о времени связывания, в языках программирования с динамическими типами данных знание о типе хранит в себе значение, а не переменная, с помощью которой осуществляется доступ к значению. Например, наша абстракция связного списка может быть определена через следующие структуры языка 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 ];
   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 ] )
    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.

Настоящая проблема возникает, когда мы хотим сделать что-либо с элементом, извлеченным из списка. Контроль типов данных, который определяет результат как принадлежащий классу 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;

  (* тип данных соответствует? *)
  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. Скрытое приведение типа данных при наследовании

Разделы

Принципиальные сложности в использовании техники, описанной в предыдущем разделе, состоят в следующем:

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

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

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. Параметризованные классы

Разделы

Последний наш тезис состоял в том, что (по крайней мере для языков со строгим контролем типа данных) само по себе наследование недостаточно для создания простых в использовании контейнерных классов. Должен применяться другой механизм. Такой механизм существует. Он заключается в определении класса с типом в качестве параметра. Такие классы называются шаблонами в C++ и обобщенными классами в некоторых других языках.

Шаблоны дают программисту возможность определять типы данных, в которых информация о типе преднамеренно остается незаданной. Этот пробел заполняется позднее. Чтобы лучше понять параметризацию, представьте себе, что описанию класса тип поставляется как аргумент процедуры или функции. Точно так же, как при вызове функции ей могут передаваться различные значения через список аргументов, так и разные «воплощения» параметризованного класса получают информацию о типе-параметре.

Параметризованное описание класса для абстракции связного списка записывается в C++ следующим образом: 

template <class T>
class List
{
public:

    void addElement(T newValue);
    T    firstElement();
    ListIterator<T> iterator();

private:

    Link<T> * firstLink;
};

template <class T>
class Link
{
public:

    T    value;
    Link *nextLink;

    Link(T, Link *);
};

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

Функции-члены, которые определяют методы в шаблоне класса, должны также описываться как шаблоны: 

template<class T>
void List<T>::addElement(T newValue)
{
  firstLink = Link new (newValue, firstLink);
}

template<class T>
T List<T>::firstElement()
{
Link first = firstLink;
T    result = first.value;

  firstLink = first->>nextLink;
  delete first;
  return result;
};

template<class T>
Link<T>::Link(T v, Link *n) : value(v); nextLink(n)
{ }

Пользователь создает различные виды списков, указывая конкретные типы. Например, следующие операторы определяют списки целых и вещественных чисел: 

List<int>  listOne;
List<double> listTwo;

Таким способом могут быть созданы только однородные списки.

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

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

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

15.5.1. Циклы и итерации в C++

Параметризованные классы

Существование механизма шаблонов как для классов, так и для индивидуальных функций позволяет определить не один, а два различных способа итераций в C++. Оба они включены в недавно разработанную стандартную библиотеку шаблонов для C++, которая рассматривается в главе 16.

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

template<class Tgt;
class List
{
public:

    typedef ListIterator<T> iterator;
    ...
    iterator begin()
     { 
      // верни мне итератор в исходном состоянии
      return ListIterator<T> (firstLink);
     }

    iterator end()
     {
      // конец
      return ListIterator<T> (0);
     }
}

template<class T>
class ListIterator
{
public:

    ListIterator (Link<T> * sl) : currentLink(sl)
     { }

    void operator ++ ()
     {
      // переход к следующему элементу
      currentLink = currentLink->nextLink;
     }

    T operator* ()
     {
      // вернуть текущий элемент
      return currentLink->value;
     }

    bool operator == (ListIterator<T> & right)
     {
      return currentLink == right.currentLink;
     }

private:

    Link<T> * currentLink;
};

Теперь итератор может быть объявлен и инициализирован заданным списком. Поэлементный цикл выполняется без знания внутренней структуры списка: 

List<int>::iterator start = aList.begin();
List<int>::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. Контейнерные классы в объектно-ориентированном программировании: успех или неудача?
  2. Структуры данных разделяются на те, которые характеризуются своей реализацией (связные списки, деревья), и на те, которые определяются их предназначением (стеки, множества). Опишите, как можно использовать ООП для упрощения второго типа структур и маскировки деталей их реализации. Приведите в качестве иллюстрации структуру данных с единым интерфейсом и двумя радикально отличающимися реализациями.
  3. Дайте пример разнородного контейнера, то есть контейнера значений различного типа.
  4. Подход Smalltalk к построению итераций состоит в том, чтобы сгруппировать операции, которые надо выполнить, в блок и передать его структуре данных. Напротив, итератор — это структура, которая передает данные одно за другим внешней процедуре, где с ними выполняются нужные действия. Можно ли реализовать подход Smalltalk в других языках программирования (Object Pascal, C++)? Как при этом сказывается строгий контроль типов?
  5. Приведите пример шаблонов, не связанных с контейнерными классами.

Учебный пример: контейнерные классы

Сайт создан в системе uCoz