Динамический массив
Динамическим называется массив, размер которого может изменяться во время исполнения программы. Возможность изменения размера отличает динамический массив от статического, размер которого задаётся на момент компиляции программы. Для изменения размера динамического массива язык программирования, поддерживающий такие массивы, должен предоставлять встроенную функцию или оператор. Динамические массивы дают возможность более гибкой работы с данными, так как позволяют не прогнозировать хранимые объёмы данных, а регулировать размер массива в соответствии с реально необходимыми объёмами.
Также иногда к динамическим относят массивы переменной длины, размер которых не фиксируется при компиляции, а задаётся при создании или инициализации массива во время исполнения программы. От «настоящих» динамических массивов они отличаются тем, что для них не предоставляются средства автоматического изменения размера с сохранением содержимого, так что при необходимости программист должен реализовать такие средства самостоятельно.
Поддержка в языках программирования
Динамические массивы могут поддерживаться либо на уровне синтаксиса самого языка программирования, либо на уровне системных библиотек. Описание динамического массива может синтаксически отличаться от описания статического, но может и быть таким же. Во втором случае, как правило, все массивы в языке являются потенциально динамическими, и только от программиста зависит, использовать ли это свойство в каждом конкретном случае. При поддержке динамических массивов посредством системных библиотек они обычно реализуются в виде классов (в смысле ООП) или обобщённых типов (так называемых «шаблонов» или «дженериков»); описание массива в этом случае представляет собой инстанцирование класса или конкретизацию обобщённого типа. В зависимости от языка, динамические массивы могут быть только одномерными массивами или иметь размерность два и более.
Поддержка динамических массивов предполагает обязательное наличие встроенной операции определения текущего размера массива. Первоначальный размер динамического массива либо равен нулю, либо задаётся при описании или инициализации. Дальнейшие изменения размера выполняются специальной встроенной операцией (процедурой). В некоторых языках (например, JavaScript, Lua) расширение массива происходит автоматически, когда делается попытка записи в несуществующую ячейку.
Реализация
Для массивов с возможностью динамического изменения размера при реализации приходится находить «золотую середину» между несколькими противоречивыми требованиями.
- Эффективность по памяти — реализация не должна приводить к существенному перерасходу памяти.
- Эффективность по производительности, которая включает в себя:
- минимальные накладные расходы на изменение размера массива;
- сохранение, по возможности, константного времени доступа на чтение/запись к элементам массива.
- Совместимость с обычными статическими массивами на низком уровне. Например, необходимым условием для применения динамического массива в вызовах функций API операционной системы может быть обязательное размещение элементов массива в непрерывном блоке физической оперативной памяти в порядке, соответствующем индексации массива. Если такое требование не выполняется, динамические массивы окажется невозможно использовать в сочетании с низкоуровневым кодом.
В зависимости от приоритета тех или иных требований выбирается отвечающий им способ реализации.
Массивы переменной длины
Реализация массивов переменной длины мало отличается от реализации обычных статических массивов. Массив элементов типа T переменной длины обычно хранится в непрерывном блоке оперативной памяти размером [math]\displaystyle{ sizeof(T) \cdot N }[/math], где N — число элементов, указываемое при описании (создании) массива. То есть описание массива переменной длины, фактически, просто маскирует динамическое выделение памяти. Разница может состоять в том, что (например, как в Си стандарта C99 и позже) массиву переменной длины выделяется память на стеке, как другим автоматическим переменным, в то время как типовой способ динамического выделения памяти (в Си — функция malloc) выделяет память в куче. Кроме того, для массива переменной длины компилятор, как правило, автоматически генерирует код освобождения памяти при выходе объявленного массива из области видимости.
Существуют различные оценки оптимальных величин для параметров алгоритма перемещения, но из общих соображений ясно, что ни один из способов их определения не гарантирует максимальной эффективности во всех случаях и для любого можно подобрать алгоритм работы с массивом, при котором перемещение будет неэффективным. Для компенсации негативных эффектов многие языки, поддерживающие динамические массивы, в командах увеличения/уменьшения массива имеют дополнительные параметры, позволяющие прямо управлять ёмкостью массива. Если программист заведомо знает, до каких размеров увеличится/уменьшится массив в результате той или иной операции, и как в дальнейшем будет происходить работа с массивом, он имеет возможность прямо указать требуемую конечную ёмкость в команде изменения размера, избежав таким образом большого количества бессмысленных перемещений.
Другие динамические алгоритмы размещения
Существует множество алгоритмов реализации динамических массивов, кроме вышеописанного. Так, возможна реализация с помощью динамических ячеек памяти, связанных ссылками, других различных структур данных. Большинство таких методов обеспечивают преимущество в каких-то определённых условиях, но либо не обеспечивает константного времени доступа, либо несовместимо со статическими массивами и поэтому не может работать с низкоуровневым кодом.
Использование
Динамические массивы используются для обработки наборов однородных данных, размер которых не известен точно на момент написания программы, но которые потенциально могут разместиться в доступной памяти. Без использования динамических массивов решение таких задач сводится к одной из стратегий:
- выделение статического массива большого размера, заведомо достаточного для полного размещения данных;
- использование статического массива в качестве буфера, в который данные загружаются частями;
- применение иных динамических структур данных (например, списков).
Примеры
Паскаль
Динамические массивы поддерживаются Delphi, FreePascal, но не Turbo Pascal.
var
byteArray : Array of Byte; // Одномерный массив
multiArray : Array of Array of string; // Многомерный массив
...
begin
...
// Установить размер одномерного массива в n элементов
SetLength (byteArray, n);
// Доступ к динамическому массиву аналогичен доступу к обычному.
// Индексация всегда начинается с нуля, индексы - всегда целые.
byteArray[0] := 10;
// Изменить размер до m элементов.
SetLength(byteArray, m);
...
// Установить размер двумерного массива в X*Y элементов
SetLength(multiArray, X, Y);
multiArray[7,35] := 'ru.wikipedia.org';
...
end.
Си
В самом языке Си нет динамических массивов, но функции стандартной библиотеки malloc, free и realloc позволяют реализовать массив переменного размера:
int *mas = (int*)malloc(sizeof(int) * n); // Создание массива из n элементов типа int
...
mas = (int*)realloc(mas, sizeof(int) * m); // Изменение размера массива с n на m с сохранением содержимого
...
free(mas); // Освобождение памяти после использования массива
Неудобство данного подхода состоит в необходимости вычислять размеры выделяемой памяти, применять явное преобразование типа и тщательно отслеживать время жизни массива (как и всегда при работе с динамически выделенной памятью в Си).
Многомерный динамический массив может быть создан как массив указателей на массивы:
int **A = (int **)malloc(N*sizeof(int *));
for(int i = 0; i < N; i++) {
A[i] = (int *)malloc(M*sizeof(int));
}
Однако рост размерности существенно усложняет процедуры создания массива и освобождения памяти по завершении его использования. Ещё более усложняется задача изменения размера массива по одной или нескольким координатам.
