Динамические массивы¶

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

¶Основные характеристики

¶Автоматическое управление памятью

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

¶Амортизированная сложность операций

Благодаря стратегии увеличения ёмкости в геометрической прогрессии (обычно в 1,5–2 раза), операция добавления элемента в конец массива имеет амортизированную временную сложность O(1). Хотя отдельное перераспределение может быть дорогим (O(n)), в среднем по всем операциям стоимость добавления одного элемента остаётся постоянной. Доступ по индексу выполняется за O(1) благодаря непрерывности памяти.

¶Различие между размером и ёмкостью

• Размер (size) — количество фактически хранящихся элементов.
• Ёмкость (capacity) — максимальное количество элементов, которое можно разместить без перераспределения памяти.

¶История

¶Ранние реализации

Концепция динамического массива восходит к языкам программирования 1960-х годов. В языке ALGOL 68 были введены «гибкие массивы» (flexible arrays), размер которых мог изменяться. Однако широкое распространение динамические массивы получили с развитием объектно-ориентированного программирования.

¶Стандартизация в C++

В 1998 году в стандарт C++ была включена библиотека STL (Standard Template Library), содержащая шаблонный класс std::vector. Он стал эталонной реализацией динамического массива, предоставляющей безопасный интерфейс с итераторами, автоматическое управление памятью и поддержку произвольного доступа. Класс std::vector остаётся одной из наиболее часто используемых структур данных в C++.

¶Распространение в других языках

В последующие десятилетия динамические массивы были реализованы во многих языках:

• Java: ArrayList (с Java 1.2, 1998 год)
• Python: встроенный тип list, который является динамическим массивом (а не связным списком, как может показаться из названия)
• C#: List<T> (с .NET Framework 2.0, 2005 год)
• JavaScript: массивы (Array) являются динамическими по умолчанию
• Rust: Vec<T> (с версии 1.0, 2015 год)

¶Реализация

¶Внутреннее устройство

Типичная реализация динамического массива содержит три поля:

1. Указатель на буфер данных в куче.
2. Целочисленное значение размера (количество элементов).
3. Целочисленное значение ёмкости (размер выделенной памяти в элементах).

¶Стратегии увеличения ёмкости

¶Операция удаления

При удалении элементов из конца массива размер уменьшается, но ёмкость обычно не уменьшается автоматически. Для освобождения неиспользуемой памяти во многих реализациях предусмотрен метод shrink_to_fit() (C++), trimToSize() (Java) или аналогичный.

¶Преимущества и недостатки

¶Преимущества

• Произвольный доступ: O(1) по индексу.
• Кэш-локальность: элементы хранятся последовательно, что обеспечивает высокую производительность при последовательном обходе.
• Простота использования: автоматическое управление размером освобождает программиста от ручного выделения памяти.
• Эффективность вставки в конец: амортизированная O(1).

¶Недостатки

• Вставка и удаление в середине: O(n) из-за необходимости сдвига элементов.
• Перераспределение памяти: может вызывать задержки при достижении предела ёмкости.
• Фрагментация памяти: при частых перераспределениях может возникать фрагментация кучи.
• Избыточное потребление памяти: зарезервированная, но неиспользуемая ёмкость может быть значительной.

¶Применение

¶В алгоритмах и структурах данных

Динамические массивы используются как основа для:

• Реализации стеков, очередей и деков (при добавлении/удалении с одного конца).
• Построения хеш-таблиц с открытой адресацией.
• Хранения данных в графах (списки смежности).
• Реализации разреженных матриц.

¶В промышленном программировании

• Обработка текстовых данных: чтение файлов, разбор строк.
• Работа с базами данных: хранение результатов запросов.
• Графические интерфейсы: списки элементов, таблицы.
• Веб-разработка: сериализация JSON-массивов.

¶В научных вычислениях

• Хранение временных рядов и сигналов.
• Представление векторов и матриц.
• Обработка изображений (пиксельные массивы).

¶Примеры в популярных языках

¶C++ (std::vector)

```cpp

¶include <vector>

std::vector<int> v = {1, 2, 3}; v.push_back(4); // Добавление в конец int x = v[2]; // Доступ по индексу ```

¶Python (list)

``python arr = [1, 2, 3] arr.append(4) # Добавление в конец x = arr[2] # Доступ по индексу ``

¶Java (ArrayList)

``java import java.util.ArrayList; ArrayList<Integer> list = new ArrayList<>(); list.add(1); list.add(2); int x = list.get(1); ``

¶Rust (Vec)

``rust let mut v = vec![1, 2, 3]; v.push(4); let x = v[2]; ``

¶Сравнение со связным списком

¶Интересные факты

• В языке Python встроенный тип list исторически назывался «массивом», но в ранних версиях (до Python 2.0) он был реализован как связный список. Переход на динамический массив произошёл в версии 2.0 (2000 год).
• В C++ std::vector гарантирует, что элементы хранятся в непрерывной памяти, что позволяет передавать указатель на первый элемент в C-функции, ожидающие обычные массивы.
• В языке Go динамические массивы называются «срезами» (slices) и являются одной из ключевых абстракций языка, используемых повсеместно.
• Стандарт C++11 ввёл семантику перемещения для std::vector, что позволило эффективно передавать большие массивы между функциями без копирования данных.

¶Источники

• Страуструп Б. «Язык программирования C++». 4-е издание, 2013.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ». 3-е издание, 2013.
• Документация C++: cppreference.com — std::vector.
• Документация Python: docs.python.org — Типы-последовательности.
• Документация Java: docs.oracle.com — ArrayList.
• Документация Rust: doc.rust-lang.org — Vec.