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

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

Также иногда к динамическим относят массивы переменной длины, размер которых не фиксируется при компиляции, а задаётся при создании или инициализации массива во время исполнения программы. От «настоящих» динамических массивов они отличаются тем, что для них не предоставляются средства автоматического изменения размера с сохранением содержимого, так что при необходимости программист должен реализовать такие средства самостоятельно.

Динамические массивы могут поддерживаться либо на уровне синтаксиса самого языка программирования, либо на уровне системных библиотек. Описание динамического массива может синтаксически отличаться от описания статического, но может и быть таким же. Во втором случае, как правило, все массивы в языке являются потенциально динамическими, и только от программиста зависит, использовать ли это свойство в каждом конкретном случае. При поддержке динамических массивов посредством системных библиотек они обычно реализуются в виде классов (в смысле ООП) или обобщённых типов (так называемых «шаблонов» или «дженериков»); описание массива в этом случае представляет собой инстанцирование класса или конкретизацию обобщённого типа. В зависимости от языка, динамические массивы могут быть только одномерными массивами или иметь размерность два и более.

Поддержка динамических массивов предполагает обязательное наличие встроенной операции определения текущего размера массива. Первоначальный размер динамического массива либо равен нулю, либо задаётся при описании или инициализации. Дальнейшие изменения размера выполняются специальной встроенной операцией (процедурой). В некоторых языках (например, JavaScript, Lua) расширение массива происходит автоматически, когда делается попытка записи в несуществующую ячейку.

Для массивов с возможностью динамического изменения размера при реализации приходится находить «золотую середину» между несколькими противоречивыми требованиями.

1. Эффективность по памяти — реализация не должна приводить к существенному перерасходу памяти.
2. Эффективность по производительности, которая включает в себя:
   • минимальные накладные расходы на изменение размера массива;
   • сохранение, по возможности, константного времени доступа на чтение/запись к элементам массива.
3. Совместимость с обычными статическими массивами на низком уровне. Например, необходимым условием для применения динамического массива в вызовах функций API операционной системы может быть обязательное размещение элементов массива в непрерывном блоке физической оперативной памяти в порядке, соответствующем индексации массива. Если такое требование не выполняется, динамические массивы окажется невозможно использовать в сочетании с низкоуровневым кодом.

В зависимости от приоритета тех или иных требований выбирается отвечающий им способ реализации.

Реализация массивов переменной длины мало отличается от реализации обычных статических массивов. Массив элементов типа T переменной длины обычно хранится в непрерывном блоке оперативной памяти размером ${\displaystyle sizeof(T)\cdot N}$, где N — число элементов, указываемое при описании (создании) массива. То есть описание массива переменной длины, фактически, просто маскирует динамическое выделение памяти. Разница может состоять в том, что (например, как в Си стандарта C99 и позже) массиву переменной длины выделяется память на стеке, как другим автоматическим переменным, в то время как типовой способ динамического выделения памяти (в Си — функция malloc) выделяет память в куче. Кроме того, для массива переменной длины компилятор, как правило, автоматически генерирует код освобождения памяти при выходе объявленного массива из области видимости.

Наиболее распространённой для типичных процедурных компилируемых языков является реализация изменения размера массива путём перемещения его в динамической памяти.

• Под массив выделяется фрагмент ОЗУ, размер которого больше требуемого т. н. логического размера (size или length). Количество элементов, которое фактически может быть размещено в этой памяти, называется ёмкостью (capacity) динамического массива. Текущая длина массива хранится в отдельном счётчике. Она может использоваться для определения текущего размера, а также для контроля выхода за границы массива, если язык поддерживает такой контроль. Таким образом, в действительности динамический массив — это массив фиксированного размера, в котором занята только часть ячеек.
• Команда увеличения размера массива, если новый размер не превышает ёмкости, просто изменяет счётчик длины массива до нужного размера. С самим массивом никаких изменений при этом не происходит.
• Команда увеличения размера, в которой новый размер превышает ёмкость, приводит к перемещению массива в памяти:

1. выделяется новый фрагмент ОЗУ, размер которого превышает размер массива;
2. содержимое массива копируется во вновь выделенную память;
3. размер и ёмкость массива актуализируются;
4. в служебной структуре, хранящей параметры массива, значение указателя на данные меняется на новое;
5. запускается команда освобождения ранее выделенного под массив фрагмент ОЗУ; если язык поддерживает автоматическое управление памятью, то освобождение ранее выделенной под массив памяти остаётся за сборщиком мусора.

• Команда уменьшения размера массива может приводить к перемещению его в памяти, если в результате её выполнения процент занятых ячеек в массиве падает ниже определённого значения. Перемещение при этом проводится по той же схеме, что и в случае команды увеличения массива.

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

• Начальная ёмкость и приращение ёмкости при увеличении размера. Может задаваться либо относительной величиной (определённая доля от логической длины массива), либо абсолютным приращением сверх требуемой длины массива. Чем больше эти параметры, тем позже, при том же режиме заполнения массива, потребуется следующее перемещение, но и тем больше памяти потенциально останется неиспользуемой. Расширение массива на любой постоянный коэффициент гарантирует, что вставка n-элементов займет O(n) времени, это означает, что каждая вставка занимает конкретное, определённое время. Численное значение этого коэффициента приводит к разным показателям: среднее время вставки операции составляет a/(a-1), в то время как число потраченных впустую ячеек составляет (a-1)n. Значение этой константы в различных приложениях и библиотеках может быть разным: во многих учебниках используют значение 2, но в реализации ArrayList языка Java используется коэффициент 3/2, в некоторых других случаях используют a=9/8.
• Минимальная ёмкость. Обычно задаётся из соображений эффективности, чтобы не терять производительность при частых изменениях размеров небольших массивов. Практически её установка означает, что все динамические массивы размером менее минимальной ёмкости в действительности будут терять память.
• Процент минимального заполнения массива. Определяет, когда будет происходить перемещение после сокращения размера массива. Чем больше эта величина, тем чаще при уменьшении размера массива будет происходить перемещение. Чем она меньше, тем больше памяти при уменьшении размера массива будет оставаться занятой, но не используемой.

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

Существует множество алгоритмов реализации динамических массивов, кроме вышеописанного. Так, возможна реализация с помощью динамических ячеек памяти, связанных ссылками, других различных структур данных. Большинство таких методов обеспечивают преимущество в каких-то определённых условиях, но либо не обеспечивает константного времени доступа, либо несовместимо со статическими массивами и поэтому не может работать с низкоуровневым кодом.

Динамические массивы используются для обработки наборов однородных данных, размер которых не известен точно на момент написания программы, но которые потенциально могут разместиться в доступной памяти. Без использования динамических массивов решение таких задач сводится к одной из стратегий:

• выделение статического массива большого размера, заведомо достаточного для полного размещения данных;
• использование статического массива в качестве буфера, в который данные загружаются частями;
• применение иных динамических структур данных (например, списков).

Первый вариант применим только когда размер набора данных меняется в небольшом, жёстко ограниченном диапазоне (например, в текстовой обработке ограничение в 1000 знаков на строку вполне приемлемо). В противном случае выбор маленького массива будет ограничивать функциональность программы, а большого (так, чтобы заведомо хватило для любых входных данных) приведёт к неэффективному расходованию памяти. Буферизация обработки усложняет алгоритм, а другие динамические структуры в задачах обработки больших последовательностей простых данных по эффективности не могут сравниться с массивом.

Использование динамических массивов позволяет выделить ровно столько памяти, сколько реально необходимо (сразу, если задача позволяет определить объём до загрузки данных, либо в процессе загрузки, расширяя массив по мере необходимости), загрузить все данные в один массив и единообразно их обработать. Недостатки, однако, имеются и у этой стратегии:

• снижение скорости работы из-за накладных расходов на изменение размера динамического массива;
• потенциальное снижение надёжности: при экстремально большом объёме входных данных попытка увеличить массив до соответствующих размеров может привести к внезапному существенному замедлению или даже отказу программы из-за недостатка свободной памяти.

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

Динамические массивы поддерживаются 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));
}

Однако рост размерности существенно усложняет процедуры создания массива и освобождения памяти по завершении его использования. Ещё более усложняется задача изменения размера массива по одной или нескольким координатам.

Некоторые компиляторы Си предоставляют нестандартную библиотечную функцию void *alloca(size_t size), несколько упрощающую работу с динамическими массивами. Эта функция выделяет память не в куче, как malloc, а на стеке, и эта память автоматически освобождается при достижении оператора return. То есть при выделении памяти динамического массива этой функцией его не нужно удалять вручную, но такой массив невозможно вернуть из функции в точку вызова.

Начиная с версии стандарта C99 в язык введены массивы переменной длины. В обычном синтаксисе описания массива Си на месте размера массива может указываться не только константа, но и переменная целого типа:

  void func(int arraySize) {
    int mas[arraySize]; // Описание массива переменной длины
    for (int i = 0; i < arraySize; ++i) {
      mas[i] = anotherFunc(i); // Обращение к элементам массива
    }
    ... 
  }

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

В стандартной библиотеке предусмотрен шаблонный класс std::vector^[1], реализующий функциональность динамического массива:

  // Объявляем массив mas, изначально содержащий числа 1 - 5:
  std::vector<int> mas = {1, 2, 3, 4, 5};

  mas.reserve(100);     // Зарезервировать место для хранения не менее 100 элементов, не изменяя фактический размер. Содержимое остаётся прежним.
  mas.resize(50);       // Задать явный размер - ровно 50 элементов. Недостающие элементы получат значение "по умолчанию", лишние элементы будут удалены.
  mas[i] = i;           // Присвоить i'му элементу значение i
  mas.push_back(100);   // Добавить элемент в конец массива
  int x = mas.back();   // Обращение к последнему элементу, в данном примере x == 100
  mas.pop_back();       // Удалить последний элемент

  std::cout << mas.size() << " " << mas.capacity() << "\n"; // Вывести ёмкость и фактический размер

  auto mas2 = mas;      // Переменная mas2 содержит полную копию mas

std::vector имеет множество методов и операторов, часть из которых показана выше на примере. Они позволяют обращаться по индексу, изменять в любую сторону размер массива, использовать его как стек, записывать новое значение в произвольную позицию массива(со сдвигом остальных элементов), и вообще поддерживать семантику типа-значения^[англ.] : копировать, обменивать, перемещать, передавать в функции и возвращать, поэлементно сравнивать с другим объектом того же типа. Управляемым является не только актуальный размер, но и ёмкость, что позволяет оптимизировать процесс выделения памяти.

std::vector реализует принцип RAII: владеет своими подобъектами, выделяет и освобождает память и правильно вызывает конструкторы/деструкторы.

Стандарт C++ требует от реализации обязательного выполнения условий:

• все элементы массива должны храниться подряд в порядке увеличения индекса в целостном блоке оперативной памяти;
• должно быть гарантировано константное время доступа к произвольному элементу.

Низкоуровневая работа с динамической памятью может реализовываться средствами, унаследованными от языка-предка, но для обеспечения типобезопасности и соблюдения требований объектной модели память под массивы рекомендуется выделять посредством специфичных для языка операторов new [] и delete []:

  // Выделение памяти под массив int длиной n
  int *mas = new int [n]; 
  ... 
  // Освобождение памяти массива
  delete [] mas;

Помимо прочего, это позволяет переопределять операторы new [] и delete [] для пользовательских типов и таким образом реализовывать собственные схемы распределения памяти.

В современном C++ ручное управление памятью является неотъемлемым фундаментом для реализации шаблонных контейнеров, однако представляет значительные трудности даже для опытных программистов, и не рекомендуется к использованию в прикладном коде.^[2][3]