Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

До освобождения памяти MyArray указывает на массив, состоящий из 42 элементов типа TMyType. Несмотря на свою простоту, приведенный метод обладает некоторыми недостатками, о которых всегда нужно помнить. Во-первых, такой код нельзя компилировать с включенной проверкой диапазонов ($R+), поскольку компилятор считает, что массив должен содержать только один элемент, а, следовательно, может использоваться только индекс 0.

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

Тем не менее, описанный метод очень широко применяется в повседневном программировании. Например, в модуле SysUnit содержится очень гибкий тип массива TByteArray, указатель на который имеет тип PByteArray. Используя этот тип (точнее сказать, указатель на тип) можно легко преобразовывать любой нетипизированный параметр, содержащийся в буфере, в массив байтов. Существуют и другие типы массивов: массив элементов типов longint, word и т.д.

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

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

Вместо этого давайте создадим структурный тип массива, TtdRecordList, который по функциям был бы аналогичен классу TList, но выделял память для самих элементов. Интерфейс такого класса приведен в листинге 2.1.

Если вы уже знакомы с интерфейсом класса TList, то наверняка обратите внимание, что класс TtdRecordList содержит все те же методы и свойства, что и TList. Таким образом, например, метод Add будет добавлять новый элемент в конец списка, a Insert - вставлять в список новый элемент в позицию с заданным индексом. Оба метода при необходимости будут приводить к расширению внутренней структуры массива, и увеличивать счетчик элементов. Метод Sort в этой главе мы рассматривать не будем. Описание его реализации будет приведено в главе 5.

Листинг 2.1. Объявление класса TtdRecordList

TtdRecordList = class

private

FActElemSize : integer;

FArray : PAnsiChar;

FCount : integer;

FCapacity : integer;

FElementSize : integer;

FIsSorted : boolean;

FMaxElemCount: integer;

FName : TtdNameString;

protected

function rlGetItem(aIndex : integer) : pointer;

procedure rlSetCapacity(aCapacity : integer);

procedure rlSetCount(aCount : integer);

function rlBinarySearch(aItem : pointer;

aCompare : TtdCompareFunc;

var aInx : integer) : boolean;

procedure rlError(aErrorCode : integer;

const aMethodName : TtdNameString;

aIndex : integer);

procedure rlExpand;

public

constructor Create(aElementSize : integer);

destructor Destroy; override;

function Add(aItem : pointer) : integer;

procedure Clear;

procedure Delete(aIndex : integer);

procedure Exchange(aIndex1, aIndex2 : integer);

function First : pointer;

function IndexOf(aItem : pointer; aCompare : TtdCompareFunc) : integer;

procedure Insert(aIndex : integer; aItem : pointer);

function InsertSorted(aItem : pointer; aCompare : TtdCompareFunc) : integer;

function Last : pointer;

procedure Move(aCurIndex, aNewIndex : integer);

function Remove(aItem : pointer; aCompare : TtdCompareFunc) : integer;

procedure Sort(aCompare : TtdCompareFunc);

property Capacity : integer read FCapacity write rlSetCapacity;

property Count : integer read FCount write rlSetCount;

property ElementSize : integer read FActElemSize;

property IsSorted : boolean read FIsSorted;

property Items[aIndex : integer] : pointer read rlGetItem; default;

property MaxCount : integer read FMaxElemCount;

property Name : TtdNameString read FName write FName;

end;

Конструктор Create сохраняет переданный ему размер элементов и вычисляет размер каждого элемента, округляя его до ближайших 4 байт. Округление будет гарантировать, что элементы всегда выровнены по границе 4 байт. Это вызвано соображениями увеличения скорости работы. В качестве последней операции, конструктор будет вычислять максимальное количество элементов, которое может содержаться в классе при заданном размере одного элемента. Фактически такая операция необходима только для Delphi1, поскольку в этой версии максимальный объем выделяемой из кучи памяти не может превышать 64 Кб и нужно убедиться, что мы не выходим за установленную границу.

Листинг 2.2. Конструктор класса TtdRecordList

constructor TtdRecordList.Create(aElementSize : integer);

begin

inherited Create;

{сохранить фактический размер элемента}

FActElemSize := aElementSize;

{округлить фактический размер элемента до 4 байт}

FElementSize := ((aElementSize + 3) shr 2) shl 2;

{вычислить максимальное количество элементов}

{$IFDEF Delphi1}

FMaxElemCount := 65535 div FElementSize;

{$ELSE}

FMaxElemCount := MaxInt div integer(FElementSize);

{$ENDIF}

FIsSorted := true;

end;

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

(В коде, приведенном в листинге 2.2, используется нестандартная директива компилятора - Delphi1. Эта директива определена во включаемом файле TDDefine.inc, который применяется во всех приведенных в книге модулях. Директиву Delphi1 намного легче запомнить, чем ее более официальное название VER80. Кроме того, официальное название сложнее запомнить, поскольку свое официальное название имеется для каждой версии. Так, например, для Delphi3 - это VER100, для Delphi4 - VER120 и т.д. Тем не менее, существуют и соответствующие неофициальное названия - Delphi3 и Delphi4.)

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

Листинг 2.3. Деструктор класса TtdRecordList

destructor TtdRecordList.Destroy

begin

Capacity := 0;

inherited Destroy;

end;

А теперь давайте перейдем к более интересным вещам: добавлению и вставке новых элементов. Реализация метода Add достаточно проста. В ней вызывается Insert для вставки нового элемента в конец массива. Метод Insert в качестве входного параметра принимает значение, представляющее собой индекс позиции, в которую требуется вставить новый элемент. Сам элемент задается указателем (есть еще один способ представления вставляемого элемента - в виде нетипизированного параметра var, однако указатели позволяют упростить реализацию и понимание других методов и, кроме того, обеспечивают непротиворечивость). При вызове метода Insert для передачи адреса вставляемого элемента в виде указателя используется операция 8, определенная в Delphi.