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