Часто приходится сталкиваться с программированием процедур, которые требуют использования массива, причем количество элементов в таком массиве заранее не известно - их может быть десять, сто или тысяча, но окончательно количество элементов будет известно только во время выполнения процедур. Более того, из-за незнания количества элементов, его трудно объявить как локальную переменную (объявление массива с максимально возможным количеством элементов может привести к перегрузке стека, особенно это касается Delphi 1). Таким образом, память под элементы массива лучше выделять из кучи.

Но даже в этом случае не все недостатки устраняются. Предположим, что вы решили, что количество элементов в массиве не может превысить 100. Но никогда не говорите "никогда", поскольку в один прекрасный день количество элементов может оказаться 101. Это приведет к перезаписи памяти или возникновению ошибок нарушения доступа (если, конечно, в коде не использовались утверждения, которые проверяли возможность превышения количества элементов над ожидаемым значением).

Одним из методов, которые уходят корнями еще к временам языка Pascal, является создание типа массива со всего одним элементом и указателя на этот массив:

type PMyArray : ATMyArray;
TMyArray : аггау[0. .0] of ТМуТуре;

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

var
MyArray : PMyArray;
begin
GetMem(MyArray, 4 2 * s i zeo f(ТМуТуре)); ... использование массива MyArray ... FreeMem(MyArray, 42*sizeof(ТМуТуре));

Обратите внимание, что процедура FreeMem при освобождении выделенного блока памяти только в Delphi 1 требует указания размера блока. Все 32-разрядные версии Delphi и Kylix хранят размер выделенного блока в самом блоке. Размер блока находится непосредственно перед блоком, который код получает с помощью процедуры GetMem. В последних версиях Delphi передаваемый в качестве входного параметра размер блока игнорируется, а вместо него используется скрытое значение.

До освобождения памяти МуАггау указывает на массив, состоящий из 42 элементов типа ТМуТуре. Несмотря на свою простоту, приведенный метод обладает некоторыми недостатками, о которых всегда нужно помнить. Во-первых, такой код нельзя компилировать с включенной проверкой диапазонов ($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;
EttaxElemCount: integer;
FName : TtdNameString;
protected
function rlGetItem(aIndex : integer) : pointer;
procedure rlSetCapacity(aCapacity : integer);
procedure rlSetCount(aCount : integer);
procedure rlError (aErrorCode : integer;
const aMethodName : TtdNameString;
alndex : integer) ; procedure rlExpand;
public
constructor Create(aElementSize : integer);
destructor Destroy;
override; function Add(altern : pointer) : integer;
procedure Clear;
procedure Delete (alndex : integer);
procedure Exchange (a Index 1, alndex2 : integer);
function First : pointer;
function IndexOf (altem : pointer;
aCompare : TtdCompareFunc) : integer;
procedure Insert (alndex : integer;
altem : pointer);
function Last : pointers-procedure Move (aCur Index, aNewIndex : integer);
function Remove (altem : pointer;
aCompare : TtdCompareFunc) : integer;
procedure Sort(aCompare : TtdCompareFunc);
property Capacity : integer read FCapacity write rlSetCapacity;
property Count : integer read FCount write rlSetCount;
property Element Size : integer read FActElemSize ; property Items [alndex : integer] : pointer read rlGetltem;
default; property MaxCount : integer read FMaxElemCount;
property Name : TtdNameString read FName write FName;
end;

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

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

constructor TtdRecordList.Create(aElementSize : integer);
begin inherited Create;
{сохранить фактический размер элемента} FActElemSize := aElementSize;
{округлить фактический размер элемента до 4 байт} FElementSize := ( (aElementSize + 3) shr 2) shl 2; {вычислить максимальное количество элементов} {$IFDEF Delphi 1}
FMaxElemCount := 65535 div FElementSize; {$ELSE}
FMaxElemCount :«= Maxlnt div FElementSize; {$ENDIF} end;

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

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

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

destructor TtdRecordList. Destroy begin
Capacity := 0;
inherited Destroy;
end;

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

Поскольку новый элемент является указателем, он может содержать nil, поэтому сначала необходимо проверить, что указатель не равен nil. Затем в реализации метода выполняется проверка выхода индекса за границы допустимого диапазона. Только после этого можно приступить к собственно вставке. Если количество элементов равно текущей емкости массива, то для расширения массива вызывается метод rlExpand Теперь мы перемещаем элементы, начиная с индекса aIndex до конца массива, на один элемент, дабы тем самым освободить место под новый элемент. И, наконец, мы вставляем элемент в образовавшуюся "дыру" и увеличиваем значение счетчика элементов на единицу.

Листинг 2.4. Добавление и вставка новых элементов

function TtdRecordList. Add (altem : pointer) : integers-begin Result := Counts-Insert (Count, altem);
ends-procedure TtdRecordList.Insert(aIndex : integer;
altem : pointer);
begin
if (altem = nil) then
rlError(tdeNilltem, 1 Insert1, aIndex);
if (aIndex < 0) or (aIndex >
Count) then
rlError(tdelndexOutOfBounds, 1 Insert1, aIndex);
if (Count = Capacity) then
rlExpand;
if (aIndex <
Count) then System.Move((FArray + (aIndex * FElementSize))A, (FArray+ (succ(alndex) * FElementSize))A, (Count - aIndex) * FElementSize);
System. Move (aItemA, (FArray + (aIndex * FElementSize))A, FActElemSize) ;

inc(FCount); ends-Реализация метода Delete, предназначенного для удаления элементов из массива, показана в листинге 2.5. Как и для Insert, сначала проверяется переданный методу индекс, затем элементы, начиная с индекса aIndex, переносятся на одну позицию к началу массива, за счет чего требуемый элемент удаляется. После удаления количество элементов в массиве уменьшается, поэтому из значения счетчика элементов вычитается единица.

Листинг 2.5. Удаление элемента массива

procedure TtdRecordList.Delete(alndex : integer);
begin
if (alndex < 0) or (alndex >= Count) then
rlError(tdelndexOutOfBounds, f Delete', alndex);
dec(FCount);
if (alndex <
Count) then System.Move((FArray+ (succ(alndex) * FElementSize))A, (FArray + (alndex * FElementSize))A, (Count - alndex) * FElementSize) ;
end;

Метод Remove аналогичен Delete в том, что с его помощью также удаляется отдельный элемент, но при этом не требуется знание его индекса в массиве. Нужный элемент находится с помощью метода indexOf и вспомогательной процедуры сравнения, которая является внешней по отношению к классу. Таким образом, метод Remove требует не только самого удаляемого элемента, но и вспомогательной процедуры, которая бы идентифицировала элемент, подлежащий удалению. Такая процедура имеет тип TdtCompareFunc. Она будет вызываться для каждого элемента массива до тех пор, пока возвращаемое значение для определенного элемента не окажется нулевым (что означает "равно"). Если процедура выполняется для всех элементов, а нулевое возвращаемое значение так и не получено, метод IndexOf возвращает значение tdcJEtemNotPresent. Листинг 2.6. Методы Remove и IndexOf

function TtdRecordList .Remove (altern : pointer;
aCompare : TtdCompareFunc) : integer;
begin
Result := IndexOf(altem, aCompare);
if (Resultotdc_ItemNotPresent) then Delete(Result);
ends-function TtdRecordList. IndexOf (altem : pointer;
aCompare : TtdCompareFunc) : integer;
var
ElementPtr : PAnsiChar;
i : integers-begin
ElementPtr := FArray;
for i : = 0 to pred(Count) do begin if (aCompare(altem, ElementPtr) = 0) then begin Result := i;
Exits-end;
inc(ElementPtr, FElementSize);
ends-Result :== tdc_I temNot Present;
end;

Для расширения массива (т.е. для увеличения его емкости) используется свойство Capacity. При его установке вызывается защищенный метод rlSetCapacity. Реализация метода несколько сложнее, чем могла бы быть. Это вызвано тем, что процедура ReAllocMem в версии Delphi 1 не делает всего того, что она делает в 32-разрядных версиях.

Соответствующий метод назван rlExpand Это защищенный метод, построенный на базе простого алгоритма и предназначенный для установки значения свойства Capacity на основе его текущего значения. Метод rlExpand вызывается автоматически при использовании метода Insert для увеличения емкости массива, если будет определено, что в настоящее время массив полностью заполнен (т.е. емкость равна количеству элементов в массиве).

Листинг 2.7. Расширение массива

procedure TtdRecordList. rlExpand; var NewCapacity : integers-begin {если текущая емкость массива равна О, установить новую емкость равной

4 элемента) if (Capacity = 0) then NewCapacity := 4

{если текущая емкость массива меньше 64, увеличить ее на 16 элементов) else if (Capacity < 64) then
NewCapacity := Capacity +16 {если текущая емкость массива 64 или больше, увеличить ее на 25%) else
NewCapacity := Capacity + (Capacity div 4) ; {убедиться, что мы не выходим за верхний индекс массива) if (NewCapacity >
FMaxElemCount) then begin
NewCapacity := FMaxElemCount;
if (NewCapacity = Capacity) then rlError (tdeAtMaxCapacity, ' rlExpand', 0);
end;
{установить новую емкость)
Capacity := NewCapacity;
ends-procedure TtdRecordList .rlSetCapacity (aCapacity : integer);
begin
if (aCapacityOFCapacity) then begin
{залрелнжь переход через максимально возможное количество элементов) if (aCapacity >
FMaxElemCount) then rlError(tdeCapacityTooLarge, 'rlSetCapacity', 0);
{повторно распределить или освободить память, если емкость массива уменьшена до нуля) {$IFDEF Delphi 1} if (aCapacity= 0) than begin
FreeMem(FArray, word(FCapacity) * FElementSize);
FArray := nils-end
else begin
if (FCapacity = 0) then
GetMem( FArray, word (aCapacity) * FElementSize) else
FArray : = ReallocMem(FArray, word(FCapacity) * FElementSize, word(aCapacity) * FElementSi ze);
end; {$ELSE)
ReallocMem(FArray, aCapacity * FElementSize); {$ENDIF)
{емкость уменьшается? если да, проверить счетчик) if (aCapacity <
FCapacity) then begin if (Count >
aCapacity) then Count :~ aCapacity;
end;
{сохранить новую емкость) FCapacity : = aCapacity;
ends-end;

Конечно, любой класс массива оказался бы бесполезным, если бы было невозможно считать элемент из массива. В классе TtdRecordList для этой цели имеется свойство Items. Единственным средством доступа для этого свойства является метод считывания rlGetltem. Во избежание ненужного копирования данных в элемент, метод rlGetltem возвращает указатель на элемент массива. Это позволяет не только считать, но и легко изменить элемент. Именно поэтому для свойства Items нет специального метода записи. Поскольку свойство отмечено ключевым словом default, доступ к отдельным элементам можно получить с помощью кода MyArray[i], а не MyArray. Items [1].

Листинг 2.8. Получение доступа к элементу массива

function TtdRecordList.rlGetltem(alndex : integer) : pointers-begin
if (alndex < 0) or (alndex >= Count) then
rlError(tdelndexOutOfBounds, •rlGetltem', alndex);
Result : = pointer(Tarray + (alndex * FelementSize));
end;

И последний метод, который мы сейчас рассмотрим, - это метод, используемый для установки свойства Count - rlSetCount. Установка свойства Count позволяет предварительно выделить память для элементов массива и работать с ней аналогично тому, как Delphi работает со стандартными массивами. Обратите внимание, что методы Insert и Delete будут автоматически изменять значение свойства Count при вставке и удалении элементов. Установка свойства Count явным образом будет гарантировать и корректную установку свойства Capacity (метод Insert делает это автоматически). Если новое значение свойства Count больше текущего, значения всех новых элементов будут равны нулю. В противном случае элементы, индексы которых больше или равны новому количеству элементов, станут недоступными (фактически их можно будет считать удаленными).

Листинг 2.9. Установка количества элементов в массиве

procedure TtdRecordList.rlSetCount(aCount : integer);
begin
if (aCountoFCount) then begin
{если новое значение количества элементов в массиве больше емкости массива, расширить массив} if (aCount >
Capacity) then
Capacity := aCount; {если новое значение количества элементов в массиве больше старого значения, установить значения новых элементов равными нулю} if (aCount >
FCount) then FillChar((FArray + (FCount * FElementSize))A, (aCount - FCount) * FElementSize, 0); {сохранить новое значение счетчика элементов} FCount := aCount;
ends-end;

Полный код класса TtdRecordList можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDRecLst.pas. В файле находятся также реализации таких стандартных методов, как First, Last, Move и Exchange.

Стандартные массивы || Оглавление || Новые динамические массивы


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



Новости за месяц

  • Декабрь
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31