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

Реализация массивов переменной длины мало отличается от реализации обычных статических массивов. Массив элементов типа 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.
• Минимальная ёмкость. Обычно задаётся из соображений эффективности, чтобы не терять производительность при частых изменениях размеров небольших массивов. Практически её установка означает, что все динамические массивы размером менее минимальной ёмкости в действительности будут терять память.
• Процент минимального заполнения массива. Определяет, когда будет происходить перемещение после сокращения размера массива. Чем больше эта величина, тем чаще при уменьшении размера массива будет происходить перемещение. Чем она меньше, тем больше памяти при уменьшении размера массива будет оставаться занятой, но не используемой.

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

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

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