Динамические массивы

5.4.1 Динамические векторы

Динамические массивы относятся к классу динамических структур. Физическое существование динамического массива реализуется в специальной области памяти, называемой куча (heap). Эта область предназначена для динамического распределения.

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

Объявление типа одномерного динамического массива, называемого также динамическим вектором, содержит только имя типа, ключевое слово array и идентификатор типа. Переменная типа «динамический вектор» объявляется обычным образом. Например, динамический вектор dinArr может быть объявлен следующим образом:

Type TdinVector = Array Of Real;

Var dinArr: TdinVector;

Если объявленный в секции Var статический массив размещается компилятором в памяти, то объявление динамического массива не приводит к отведению памяти для него. В памяти лишь резервируется 4‑байтовая ячейка, в которую будет занесен адрес динамически создаваемого участка памяти. Сам участок памяти для динамического массива создается при выполнении процедуры SetLength.

Для создания динамического вектора в функцию SetLength в качестве аргументов передаются имя массива и целая неотрицательная величина, значение которой равно количеству элементов создаваемого массива. Например, результатом вызова

SetLength(dinArr, 10);

будет выделение для вектора dinArr участка памяти под 10 элементов типа Real и задает всем элементам нулевые значения. Индексы динамического массива - всегда целые числа, начинающиеся с нуля. Поэтому в приведенном примере вектор состоит из элементов от dinArr[0] до dinArr[9].

Повторное применение SetLength к уже существующему массиву изменяет его размер. Если новое значение размера больше предыдущего, то все предыдущие значения элементов сохраняются, и в конце массива добавляются новые нулевые элементы базового типа. Если же новый размер меньше предыдущего, то массив усекается «справа» и в нем остаются значения начальных элементов. Усечение можно проводить функцией Copy, присваивая ее результат самому массиву, например, вызов

dinArr:= Copy(dinArr, 0, 3);

усекает динамический вектор dinArr, оставляя неизменными первые три его элемента.

Сама переменная динамического массива (в нашем примере это переменная dinArr) является указателем на начало массива. Если место под массив еще не выделено, значение этой переменной равно Nil. Операция сравнения А = В двух динамических массивов даст True только в том случае, если А и В указывают на один и тот же массив. Но это не совсем обычный указатель. Его нельзя, например, разыменовать операцией ^ , нельзя передать в процедуры New и Dispose.

Удалить из памяти динамический массив можно одним из следующих способов:

- присвоить ему значение Nil, например, dinArr:= Nil;

- использовать функцию Finalize: Finalize(dinArr);

- установить функцией SetLength нулевую длину, например,

SetLength(dinArr, 0);

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

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

SetLength(D, 3);

SetLength(С, 4);

SetLength(D, 6);

где D и С - динамические векторы с одинаковым базовым типом. Тогда в результате выполнения второго вызова SetLength(С, 4) участок памяти для С будет создан сразу после участка вектора D, созданного при первом вызове SetLength(D, 3). Третий вызов должен увеличить участок для размещения нового вектора D. Поскольку новый участок должен превосходить старый вдвое, то «старых» ячеек ему будет недостаточно. Поэтому третий вызов приведет к появлению нового участка, содержащего смежные слоты элементов вектора D, и этот участок будет расположен после участка отведенного ранее для вектора С.

5.4.2 Многомерные динамические массивы

Многомерный динамический массив размерности М определяется как динамический вектор динамических массивов размерности М-1, динамический массив размерности М-1 является вектором динамических массивов размерности М-2 и т. д. Например, нотации

Type TdinMatr = Array Of Array Of Integer;

Var arrMatr: TdinMatr;

описывают двумерный динамический массив (динамическую матрицу).

Один из способов отвести память под такой массив - использовать процедуру SetLength. Если требуется зафиксировать диапазоны изменения всех индексов, то в функцию SetLength следует передавать столько размеров, сколько раз повторяется слово Array в объявлении типа создаваемого многомерного динамического массива. Например, оператор

SetLength(arrMatr, 3, 5);

отводит память под прямоугольную матрицу arrMatr, состоящую из трех строк и пяти столбцов.

Индексы существующего динамического массива отсчитываются от нуля.

Можно изменять диапазоны некоторых индексов в зависимости от значений других индексов. Например, можно создать матрицу, у которой в зависимости от номера строки варьируется длина строки. В этом случае сначала процедурой SetLength фиксируется диапазон первого индекса. Если диапазон изменения первого индекса нужно установить [0, 2], то следует записать вызов SetLength в виде:

SetLength(arrMatr, 3);

При выполнении этого вызова в памяти отводится место для трех переменных arrMatr[0], arrMatr[1] и arrMatr[2]. Затем можно задать размер, например, второго из этих массивов, т. е. фактически количество элементов второй строки динамического двумерного массива (строки с индексом 1). Следующий оператор устанавливает этому размеру значение 5:

SetLength(arrMatr[1], 5);

Программный фрагмент, приведенный ниже, уменьшает размер строки с ростом ее индекса:

Var arrMatr: TdinMatr;

N, i, j, m: Integer;

Begin

N:= 3; m:= 1;

SetLength(arrMatr, N);

For i:= 0 To N-1 Do Begin

SetLength(arrMatr[i], N-i);

For j:= 0 To N-i-1 Do Begin

arrMatr[i, j]:= m;

Inc(m);

End;

End;

End;

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

Рисунок 5.2 - Логическая структура динамической матрицы arrMatr,
содержащей строки различных размеров

Физическая структура массива приводится на рисунке 5.3. Как показывает этот рисунок, для всего массива в сегменте статических данных для массива выделяется 4-хбайтовая ячейка, в которую помещается указатель (адрес) на вектор (arrMatr[0], arrMatr[1], arrMatr[2]), элементы которого располагаются в куче, занимая последовательные 4-хбайтовые ячейки. В этих ячейках содержатся ссылки на слоты соответствующих строк, а сами слоты размещаются в куче в непредсказуемом «порядке». Элементы каждой строки располагаются в слотах строки последовательно друг за другом. В ячейки элементов заносятся из значения.

Рисунок 5.3 - Физическая структура динамической матрицы arrMatr,
содержащей строки различных размеров