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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Увеличение размера массива происходит быстро пока он меньше объёма массива. Когда нужно увеличить размер массива, а свободного места в нём нет, создаётся ещё один массив большего объема, все элементы старого объема копируются в новый массив, ссылка на старый массив удаляется. На картинке помечено черепахами.

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

Динамические массивы ограниченного размера и их объём[править | править вики-текст]

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

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

Геометрическое расширение и амортизация стоимости затрат[править | править вики-текст]

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

function insertEnd(dynarray a, element e)
    if (a.size = a.capacity)
        // resize a to twice its current capacity:
        a.capacity ← a.capacity * 2  
        // (copy the contents to the new memory location here)
    a[a.size] ← e
    a.size ← a.size + 1  

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

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

Примеры[править | править вики-текст]

Паскаль[править | править вики-текст]

Динамические массивы (или массивы переменной длины) поддерживаются Delphi, FreePascal, но не Turbo Pascal.

 byteArray : Array of Byte; // Одномерный массив
 multiArray : Array of Array of string;  // Многомерный массив

Указываем размер массива в 10 элементов:

 SetLength (byteArray, 10);

C и C++[править | править вики-текст]

Одномерный динамический массив[править | править вики-текст]

Создаем массив с 10-ю элементами типа int:

Си:

        int *mas = malloc (sizeof(int) * 10);

С++:

        int *mas = new int[10];

Освобождение памяти из-под одномерного динамического массива:

Си:

      free(mas);

С++: оператор delete:

      delete []mas;

Строго говоря вышеописанная реализация массива не является динамической, так как нет изменения размера массива во время работы, а всего лишь массив переменной длины. Возможным решением является realloc, но можно применить только при использовании malloc, но не new. Для того чтобы изменить размер такого массива необходимо объявить ещё один массив нужного размера, скопировать в него все данные и освободить память, занимаемую старым массивом. В С++ библиотечным решением является std::vector. В С89 нет массивов переменной длины, они есть только в С99 (который поддерживают не все компиляторы). Некоторые (довольно старые) компиляторы С++ также не поддерживают массивов переменной длины.

Двумерный динамический массив[править | править вики-текст]

Двумерный динамический массив в языке Си может быть создан как массив указателей на массивы строк, при этом память как под массив указателей, так и под массивы строк должны быть выделены динамически:

int **A = (int **)malloc(N*sizeof(int *));
for(int i = 0; i < N; i++) {
    A[i] = (int *)malloc(M*sizeof(int));
}

Ссылки[править | править вики-текст]