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

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;

end;

procedure TtdRecordList.rlSetCapacity(aCapacity : integer);

begin

if (aCapacity <> FCapacity) then begin

{запретить переход через максимально возможное количество элементов}

if (aCapacity > FMaxElemCount) then

rlError(tdeCapacityTooLarge, 'rlSetCapacity', 0);

{повторно распределить или освободить память, если емкость массива уменьшена до нуля}

{$IFDEF Delphi1}

if (aCapacity= 0) than begin

FreeMem(FArray, word(FCapacity) * FElementSize);

FArray := nil

end

else begin

if (FCapacity = 0) then

GetMem( FArray, word (aCapacity) * FElementSize) else

FArray := ReallocMem(FArray,

word(FCapacity) * FElementSize,

word(aCapacity) * FElementSize);

end;

{$ELSE}

ReallocMem(FArray, aCapacity * FElementSize);

{$ENDIF}

{емкость уменьшается? если да, проверить счетчик}

if (aCapacity < FCapacity) then begin

if (Count > aCapacity) then

Count := aCapacity;

end;

{сохранить новую емкость}

FCapacity := aCapacity;

end

end;

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

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

function TtdRecordList.rlGetItem(aIndex : integer): pointer;

begin

if (aIndex < 0) or (aIndex >= Count) then

rlError(tdeIndexOutOfBounds, 'rlGetItem', aIndex);

Result := pointer(FArray + (aIndex * FElementSize));

end;

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

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

procedure TtdRecordList.rlSetCount(aCount : integer);

begin

if (aCount <> FCount) then begin

{если новое значение количества элементов в массиве больше емкости массива, расширить массив}

if (aCount > Capacity) then

Capacity := aCount;

{если новое значение количества элементов в массиве больше старого значения, установить значения новых элементов равными нулю}

if (aCount > FCount) then

FillChar((FArray + (FCount * FElementSize))^, (aCount - FCount) * FElementSize, 0);

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

FCount := aCount;

end;

end;

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

Новые динамические массивы

В Delphi 4 компания Borland ввела динамические массивы - расширение языка, которое позволило использовать массивы, размер которых на этапе программирования не известен. Код, вносимый компилятором в приложение, аналогичен тому, который используется для длинных строк. Как и для строк, размер массива можно установить с помощью стандартной процедуры SetLength. Кроме того, динамические массивы ведут счетчики ссылок. И даже больше, функция Copy перегружена, что позволяет копировать отдельные части массива. Как и для стандартных статических массивов, доступ к отдельным элементам осуществляется с помощью операции [].

В настоящей книге мы не будем подробно рассматривать динамические массивы. Их применение ограничено, поскольку они доступны только в версиях, начиная с Delphi 4 и Kylix. И, кроме того, они не имеют той функциональности, которую нам предоставляет класс TtdRecordList. Если вы хотите больше узнать о динамических массивах, изучите документацию по своей версии Delphi.

Класс TList, массив указателей

С самой первой версии в Delphi существовал еще один стандартный массив -класс TList. В отличие от всех ранее нами рассмотренных массивов, TList представляет собой массив указателей.

Краткий обзор класса TList

Класс TList хранит указатели в формате массива. Указатели могут быть любыми. Они могут указывать на записи, строки или объекты. Класс имеет специальные методы для вставки и удаления элементов, поиска элемента в списке, перестановки элементов и, в последних версиях компилятора, для сортировки элементов в списке. Как и любой другой массив, TList может использовать операцию [ ]. Поскольку свойство Items является свойством по умолчанию, то для получения доступа к указателю с индексом i вместо MyList.Item[i] можно записывать MyList[i]. Индексация в классе TList всегда начинается с 0.

Несмотря на высокую гибкость класса TList, иногда при его использовании возникают проблемы.

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

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

for i := 0 to pred(MyList.Count) do begin

if SomeConditionApplies(i) then begin

TObject(MyList[i]).Free;

MyList.Delete(i);

end;

end;

где ScmeConditionApplies - некоторая произвольная функция, которая определяет, удалять или нет элемент с индексом i.

Все мы привыкли к тому, что значение переменной цикла должно увеличиваться. Именно в этом-то и заключается ошибка. Предположим, что в массиве находится три элемента. В таком случае код в цикле будет выполнен три раза: для индексов 0, 1 и 2. Пусть при первом выполнении цикла условие выполняется. При этом освобождается объект с индексом 0, а затем элемент с индексом 0 удаляется из списка. После первого выполнения цикла в списке остается два элемента, но их индексы теперь 0 и 1, а не 1 и 2. При втором выполнении цикла, при соблюдении условия, освобождается объект с индексом 1 (который, если вы помните, был изначально элементом с индексом 2), после чего удаляется элемент с индексом 1. После этого в списке остается всего один элемент. И его индекс 0. При третьем выполнении цикла код пытается освободить память, ранее выделенную под объект, индекс которого 2, и в результате генерируется исключение "list index out of bounds".

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

Для освобождения всех элементов списка используется следующий код, а не вызов метода Delete для каждого элемента:

for i := 0 to pred(MyList.Count) do

TObject(MyList[i]).Free;

end;

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

При первом написании предыдущего параграфа автор книги не знал, что компания Borland сделала с классом TList в версии Delphi 5. В Delphi 5 по каким-то непостижимым причинам было изменено функционирование класса TList с целью обеспечения поддержки нового производного класса - TObjectList.TObjectList предназначен для хранения экземпляров объектов. Он находится в модуле Contnrs, о котором мы поговорим чуть позже.