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

Общее понятие и назначение

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

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

Индексация элементов динамического массива совпадает с индексацией обычного статического массива: каждый элемент имеет индекс, принадлежащий диапазону $0 \le i \le n-1$ .

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

Выделение и освобождение памяти

При создании динамического массива в оперативной памяти выделяется блок байтов, размер которого обычно рассчитывают как $n \cdot \mathrm{sizeof}(T)$ , где T — тип элементов. В языках низкого уровня это делается с помощью системных вызовов или функций выделения памяти (например, malloc/realloc/free в C), в языках высокого уровня — через операторы языка или стандартные контейнеры.

Capacity (ёмкость) - максимальное число элементов, которое может храниться в текущем выделенном блоке памяти без повторного выделения и копирования данных.

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

Пример: если есть базовый адрес блока памяти, адрес i-го элемента вычисляется как $\mathrm{base} + i \cdot \mathrm{sizeof}(T)$ , что обеспечивает быстрый доступ по индексу.

Доступ к элементам и индексирование

Доступ к любому элементу динамического массива по индексу выполняется за константное время, что формально записывают как $O(1)$ . Это одно из ключевых преимуществ массивов перед, например, связанными списками.

Size (текущий размер) - количество реально хранящихся элементов в массиве в текущий момент; всегда не превышает capacity.

При обращении к элементу важно проверять, что индекс находится в допустимом диапазоне, иначе возможен выход за пределы выделенной памяти и непредсказуемое поведение программы. Условие допустимости индекса обычно формулируется как $0 \le i \le n-1$ или в другой форме $\text{size} = \text{capacity}$ .

Изменение размера: стратегия перераспределения

Когда количество элементов достигает текущей ёмкости, требуется выделить новый блок памяти и скопировать туда существующие элементы. Простая стратегия — удвоение ёмкости (doubling), при которой новая ёмкость равна удвоенной старой: $C_{new} = 2\, C_{old}$ . Альтернативой может быть умножение на любой коэффициент α>1: $C_{new} = \lceil \alpha C_{old} \rceil, \ \alpha>1$ .

При таких стратегиях количество копирований при последовательном добавлении множества элементов растёт не пропорционально квадрату, а суммарная стоимость копирования элементов за серию операций остаётся линейной по числу добавленных элементов, что даёт амортизированную константу на операцию. Один из способов формально показать это — оценить суммарное число копий и получить не больше значения, выражаемого формулой $\mathrm{total\_copies} \le 2n$ .

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

Пример: последовательное добавление n элементов в пустой массив при стратегии удвоения приведёт к росту ёмкости по степеням двойки: $C_k = 2^k C_0$ . При этом суммарное число перемещённых элементов ограничено линейной функцией от n.

Вставка и удаление внутренних элементов

Вставка элемента не в конец массива, а в произвольную позицию требует сдвига всех последующих элементов на одну позицию вправо, что приводит к линейной по числу сдвигов стоимости операции, обычно оцениваемой как $\text{cost} = n$ или, в асимптотической нотации, $O(n)$ при вставке у начала.

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

Пример: при удалении элемента по индексу i все элементы с индексами > i перемещаются на одну позицию влево, что эквивалентно обновлению значений в диапазоне до конца массива; адреса соседних элементов отличаются на величину $\text{addr}(i+1)-\text{addr}(i)=\mathrm{sizeof}(T)$ .

Фрагментация, перенос данных и безопасность указателей

Повторные выделения и освобождения памяти могут приводить к внешней фрагментации heap-памяти; это не влияет на логическую корректность массива, но может увеличить общее потребление памяти и снизить производительность. При реаллокации старый блок освобождается или остаётся, а данные копируются в новый — все старые указатели на элементы становятся недействительными.

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

Сжатие и уменьшение ёмкости

Иногда после удаления большого числа элементов имеет смысл уменьшить capacity, чтобы вернуть излишне зарезервированную память системе. Простейшее правило сжатия — уменьшать ёмкость, когда $\text{size} < \dfrac{\text{capacity}}{4}$ , с последующим перераспределением памяти на меньший блок. Однако агрессивное уменьшение может привести к частым перераспределениям при колебаниях размера, поэтому применяют пороги и гистерезис.

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

Практические советы и типичные ошибки

Всегда храните отдельно size и capacity: size — реальное число элементов, capacity — размер выделенного блока. При обращении по индексу проверяйте границы и помните, что при reallocation все ранее полученные указатели становятся недействительными.

Не пытайтесь вручную рассчитывать смещение в байтах, полагаясь на выравнивание и padding без учёта спецификации языка и архитектуры; используйте стандартные функции sizeof и безопасные методы доступа. При использовании встроенных контейнеров (например, ArrayList, std::vector) изучите контракт по инвалидированию итераторов и гарантиям сложности операций.

Пример использования: при реализации метода push_back сначала проверяется условие $\text{size} = \text{capacity}$ (или эквивалентное), и при совпадении выполняется расширение ёмкости, копирование элементов и обновление указателей, после чего новый элемент записывается в массив; в обычном случае элемент просто помещается по индексу size и затем size увеличивается на единицу.

Иллюстрации и визуализация

Для более наглядного понимания структуры полезно представить блок памяти как непрерывную линию адресов с пометками выделенной и свободной памяти, а также указателями на начало, текущий размер и ёмкость. Ниже могут быть приведены схемы распределения памяти и шаги при реаллокации: {IMAGE_0}.

Ещё одна полезная иллюстрация — граф изменения capacity при последовательном добавлении элементов при стратегии удвоения, где видно экспоненциальный рост резервируемой ёмкости по операциям вставки и соответствующее ограничение суммарной стоимости пересылок: см. схему {IMAGE_1}.

Основные

Курсы

Другое