Контейнеры и их объектная реализация

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

Начнем с описания простейшего контейнерного класса, реализованного на базе обычного массива. Введем следующий класс:

TContainer = class

private

Arrs: array [1..100] of TFigure; // массив полиморфных указателей

// на графические фигуры;

count: integer; // текущее число объектов в контейнере

public

constructor Create;

function GetCount: integer;

function Add (aFig: TFigure; ai: integer): integer;

function Delete (ai: integer): integer;

function Search (aFig: TFigure): integer;

procedure ShowAll;

procedure MoveAll (dx, dy: integer);

procedure FreeAll;

end;

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

Логика реализации основных методов вполне очевидна и описывается ниже.

1. Конструктор создает массив пустых указателей и устанавливает count в ноль.

2. Метод добавления выполняет следующие действия:

· проверят возможность добавления;

· проверят параметр-индекс ai на допустимость;

· при необходимости сдвигает хвостовую часть массива вправо на одну позицию;

· записывает в ячейку ai значение параметра aFig;

· увеличивает счетчик count.

3. Метод удаления выполняет следующие шаги:

· проверят возможность удаления;

· проверят параметр-индекс удаляемого элемента ai;

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

· уменьшает счетчик count.

Использование объекта-контейнера включает в себя следующие шаги:

· объявить объект-контейнер:

var Cont: TContainer;

· создать пустой контейнер с помощью конструктора:

Cont:= TContainer.Create;

· добавить в контейнер необходимые объекты:

Cont.Add (MyCirc, 5);

Cont.Add (MyRect, 10);

· циклически обработать контейнер:

Cont.ShowAll;

Cont.MoveTo (…);

· очистить контейнер:

Cont.FreeAll;

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

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

DynArrs: arrayof TFigure;

При обработке этой строки компилятор выделяет память только для переменной DynArrs, которая является указателем на будущий массив. Кроме того, добавим закрытое свойство для хранения текущей размерности (мощности) массива:

capacity: integer;

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

Конструктор создает начальный массив некоторой заданной мощности (например, 100 элементов) с помощью стандартной программы SetLength:

SetLength (DynArrs, 100);

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

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

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

Можно предложить и другую реализацию контейнера – на основе линейного списка полиморфных указателей.

			последний элемент nil = null = 0 адрес объекта

	объект окружность		объект линия		объект прямоугольник		объект окружность

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

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

Описание класса элементов списка (для разнообразия используем язык Java):

class Item

{ private Item Next; // свойство-указатель на следующий элемент

private Figure Fig; // свойство-указатель адресуемой фигуры

public Item (Item aNext, Figure aFig)

{ Next = aNext; Fig = aFig; }

public Item GetNext () {return Next;}

public Figure GetFig () {return Fig;}

public void SetNext (Item aNext) { Next = aNext;}

public void SetFig (Figure aFig) { Fig = aFig;}

};

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

Описание класса контейнерного списка (для простоты некоторые методы не реализованы):

class List

{ private Item First; // указатель на первый элемент списка

public List() { First = null;} // конструктор создает пустой список

publicvoid Add(Figure aFig); // для простоты добавляем всегда в

// начало списка

{ First = new Item(First, aFig);}

publicvoid ShowAll ()

{ Item Current = First;

while (Current!= null)

{ Current.GetFig().Show();

Current = Current.GetNext();

} // конец цикла

} // конец метода отображения

}; // конец описания класса

Особого комментария в методе добавления опять заслуживает использование полиморфных указателей. Объектный указатель Current адресует текущий объект-элемент списка и с помощью метода доступа GetFig() извлекает из элемента указатель на присоединенный объект-фигуру, с помощью которого выполняется вызов виртуального (полиморфного) метода отображения Show.

Использовать список-контейнер можно следующим образом:

List MyList = new List(); // создание пустого контейнера

МуList.Add(MyCircle);

MyList.Add(MyRect);

…..

MyList.ShowAll (…);

В заключение отметим, что в стандартных библиотеках классов, поддерживающих объектные языки, реализованы стандартные контейнеры. В качестве примера рассмотрим основные контейнеры библиотеки VCL языка Delphi Pascal.

Основой всех контейнеров является класс TList как динамический массив нетипизированных указателей, позволяющий собирать в одну структуру как объекты разных классов, так и необъекты (например, обычные записи). Описание этого класса обычно находится в файле C:\Program Files\Borland\Delphi7\Source\Rtl\Common\Classes.pas (это модуль Classes). В классе реализовано множество полезных методов: добавление в конец (Add), добавление перед заданным элементом (Insert), удаление по индексу (Delete), удаление по указателю (Remove), перестановка двух элементов (Exchange), перемещение элемента в новое место (Move), поиск элемента по указателю (IndexOf) и др. Объекты класса TList очень широко используются внутри библиотеки VCL в качестве свойства-контейнера в различных классах.

Стандартная схема использования объектов класса TList включает в себя:

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

· добавление/удаление элементов в контейнер;

· циклическая обработка контейнера с доступом к элементам с помощью конструкции List[i];

· удаление контейнера с помощью метода Free.

В том же файле Classes.pas реализованы еще несколько контейнерных классов, в частности, абстрактный класс TStrings для обработки текстовых строк и класс TStringList как массив пар указателей на текстовые строки и связанные с ними объекты. Еще одной полезной парой классов являются классы TCollection и TCollectionItem.

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

Небольшой комментарий к некоторым классам в этой иерархии. Класс TObjectList определяет список-массив указателей на объекты, построенный на основе класса TList. Абстрактный класс TOrderedList ограничивает функциональность общего списка добавлением и удалением элементов только с концов набора и поэтому является основой «рабочих» классов для стека и очереди указателей общего типа (TStack и TQueue) и указателей только на объекты (TObjectStack и TObjectQueue). Наконец, классы TBucketList и TObjectBucketList реализуют структуру хеш-таблицы.

В базовых библиотеках классов JFC и.NET Framework реализовано более десяти различных вариантов контейнеров (коллекций), построенных на основе более современных принципов, в частности – с активным использованием механизма интерфейсных классов. Этот механизм является одним из важнейших в современной реализации объектной технологии и поэтому рассматривается отдельно в следующей теме, где также приводится краткое описание библиотеки коллекций языка Java.