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

type

PMyArray : ^TMyArray;

TMyArray : array[0..0] of TMyType;

Теперь, если нам необходим массив типа TMyType, можно легко указать требуемое количество элементов:

var

MyArray : PMyArray;

begin

GetMem(MyArray, 42 * sizeof(TMyType));

... использование массива MyArray...

FreeMem(MyArray, 42*sizeof(TMyType));

Обратите внимание, что процедура FreeMem при освобождении выделенного блока памяти только в Delphi1 требует указания размера блока. Все 32-разрядные версии Delphi и Kylix хранят размер выделенного блока в самом блоке. Размер блока находится непосредственно перед блоком, который код получает с помощью процедуры GetMem. В последних версиях 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;