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

TL;DR

Динамический массив (dynamic array, resizable array, vector) — это непрерывный буфер, который хранит n элементов и имеет ёмкость c ≥ n; при переполнении буфер заменяется буфером большей ёмкости, а элементы копируются. Доступ по индексу и изменение элемента стоят O(1), вставка и удаление в середину — O(n), а push_back при геометрическом росте ёмкости (например, c ← 2c) имеет амортизированную стоимость O(1). Главная идея — редко платить за копирование и раскладывать эту плату на много дешёвых операций; арифметический рост c ← c + k этой цели не достигает и даёт Θ(n) амортизированно.

Свойство	Значение
Класс	Последовательный контейнер на непрерывном буфере
Изобретение	Как структура данных не имеет одного автора; амортизированный анализ динамических таблиц — CLRS, гл. 17 [1]; `std::vector` — STL C++ [3]
Доступ по индексу	`O(1)`
`push_back` / `pop_back`	`O(1)` амортизированно, `O(n)` в худшем случае
Вставка / удаление в середину	`O(n)`
Поиск	`O(n)` без упорядоченности; `O(log n)` в отсортированном массиве
Память	`O(n)` элементов плюс запас ёмкости; сразу после геометрического роста `c ≤ αn`, после удалений или `reserve` запас может быть больше
Упорядоченность	Порядок вставки; индекс задаёт позицию
Стабильность / детерминированность	Детерминирован; адреса элементов меняются при реаллокации
Альтернативы	Связный список, дека, rope, хеш-таблица, фиксированный массив
Где встречается	`std::vector`, `ArrayList`, `list` Python, `Vec` Rust, буферы парсеров и сетевых стеков

Определения

Динамический массив — последовательный контейнер, хранящий элементы в непрерывном буфере data[0..c−1], где n — число элементов, а c ≥ n — ёмкость. Формально это тройка (data, n, c) с инвариантом 0 ≤ n ≤ c; элементы data[0..n−1] идут в порядке индексов.

Размер (size) — число хранимых элементов n. Ёмкость (capacity) — число слотов, выделенных в буфере c. Всегда n ≤ c; разность c − n — свободный запас.

Коэффициент заполнения (load factor) — отношение n/c. При n = c буфер полон, и следующая вставка требует реаллокации.

Реаллокация — выделение нового буфера ёмкости c' > c, перенос в него n элементов и освобождение старого буфера. Перенос может быть копированием или перемещением.

Коэффициент роста (growth factor) — множитель α > 1, задающий c' = αc (обычно α = 2 или α = 1.5). При арифметическом росте c' = c + k для фиксированного k.

Амортизированная стоимость — средняя стоимость операции на длинной серии, в которой дорогие реаллокации встречаются редко. Формально для серии из m операций с суммарной стоимостью T(m) амортизированная стоимость одной операции равна T(m)/m.

reserve(c) — заранее выделить ёмкость не меньше c, не меняя размер. shrink_to_fit — попытаться уменьшить ёмкость до размера (реализация может проигнорировать запрос).

Обозначения. n — размер; c — ёмкость; α — коэффициент роста; m — число операций; log — двоичный логарифм. Стоимость считаем в «элементарных операциях»: запись элемента, чтение, копирование.

Мотивация и интуиция

Фиксированный массив требует знать размер заранее. Если выделить «с запасом», память тратится впустую; если выделить ровно n, любая вставка сверх n невозможна. Динамический массив решает обе задачи: он хранит ёмкость c отдельно от размера n и увеличивает c только тогда, когда свободных слотов нет.

Наивное решение — при каждой вставке увеличивать ёмкость на один и копировать все элементы — плохо. При m вставках в пустой массив копируется 0 + 1 + 2 + … + (m−1) = m(m−1)/2 элементов, то есть Θ(m²), а одна вставка в среднем стоит Θ(m). Для m = 10^6 это порядка 5·10^11 копий — неприемлемо. Сравнение суммарных копий при +1 и ×2 показано на рис. 3.

Ключевая идея: удваивать ёмкость. Тогда копирования происходят на размерах 1, 2, 4, 8, …, и суммарное число копий меньше 2m. Дорогие операции редки, а средняя стоимость одной вставки остаётся константной. Именно этот приём — геометрический рост — лежит в основе std::vector, ArrayList, list Python и Vec Rust.

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

Устройство

Динамический массив хранит три величины:

data — указатель на непрерывный буфер;
n — размер (сколько элементов действительно хранится);
c — ёмкость (сколько элементов помещается без реаллокации).

Инварианты, которые поддерживают все операции:

0 ≤ n ≤ c;
элементы data[0..n−1] непрерывны и идут в порядке индексов;
data[n..c−1] — свободные слоты, значения в них не считаются элементами;
при геометрическом росте c не меньше n и не больше αn (с точностью до начальной ёмкости).

Размер и ёмкость — разные величины. Например, буфер может иметь c = 8, а хранить n = 5 элементов; тогда три слота свободны, и следующая вставка не требует реаллокации. Это показано на рис. 1.

Рис. 1. Буфер ёмкостью 8 и размером 5: занятые слоты 0–4, свободные 5–7; size и capacity — разные величины.

См. рис. 1: size = 5 указывает, что элементы 10, 20, 30, 40, 50 — действительные данные, а слоты 5–7 — резерв. Если добавить 60, она попадёт в слот 5 без копирования; если добавить ещё три элемента, буфер заполнится и потребуется реаллокация.

Операции и алгоритмы

Операция: доступ и изменение по индексу

Идея. Адрес элемента вычисляется арифметически: data + i * sizeof(T). Поэтому доступ не зависит от n.

Шаги.

Проверить 0 ≤ i < n.
Вернуть data[i] или записать в него новое значение.

Инвариант. Индекс i указывает на тот же логический элемент; границы не нарушены.

Псевдокод.

Алгоритм Get(A, i)
Вход:  A — динамический массив; i — индекс
Выход: A[i]
Инвариант: 0 ≤ i < A.n

1  if i < 0 or i ≥ A.n
2      error "индекс вне диапазона"
3  return A.data[i]

Сложность: O(1) времени, O(1) дополнительной памяти.
Корректность: адрес элемента — A.data + i, элементы непрерывны.

Пример. В массиве [10, 20, 30, 40, 50] доступ A[2] возвращает 30, A[4] = 99 заменяет 50 на 99. Оба действия не двигают другие элементы.

Сложность. Время O(1), память O(1). В худшем случае — тоже O(1): арифметика адреса и одно чтение/запись.

Крайние случаи. Пустой массив: любой индекс недопустим. Отрицательный индекс отклоняется. Для i = n доступ недопустим, хотя слот может существовать: он ещё не элемент.

Рисунок. См. рис. 1.

Операция: вставка в конец (`push_back`)

Идея. Если есть свободный слот, записать элемент за последним. Если буфер полон, выделить буфер большей ёмкости, перенести элементы и только затем записать новый.

Шаги.

Если n = c, выполнить реаллокацию: c' = max(1, αc).
Перенести data[0..n−1] в новый буфер.
Освободить старый буфер, заменить data и c.
Записать новый элемент в data[n], увеличить n на 1.

Инвариант. После шага 4 выполнено n ≤ c; старые элементы сохранили порядок; новый элемент стоит последним.

Псевдокод.

Алгоритм Push-Back(A, x)
Вход:  A — динамический массив; x — элемент
Выход: A с добавленным x
Инвариант: 0 ≤ A.n ≤ A.c

1  if A.n = A.c
2      newCap ← max(1, 2·A.c)              # геометрический рост
3      newData ← выделить newCap слотов
4      for i ← 0 to A.n − 1
5          newData[i] ← A.data[i]
6      освободить A.data
7      A.data ← newData;  A.c ← newCap
8  A.data[A.n] ← x
9  A.n ← A.n + 1

Сложность: O(1) амортизированно, O(n) в худшем случае (реаллокация).
Корректность: старые элементы скопированы в том же порядке; x записан за ними.

Пример. Массив [10, 20, 30, 40] имеет n = c = 4. При добавлении 50 выделяется буфер ёмкости 8, копируются 10, 20, 30, 40, затем 50 записывается в слот 4. Новый размер n = 5, ёмкость c = 8 (рис. 2).

Рис. 2. Append при size = capacity = 4: новый буфер ёмкости 8, копирование четырёх элементов и запись нового; старый буфер освобождается.

Рис. 3. Суммарные копии при 16 вставках: рост на единицу даёт 120 копий, удвоение — 15.

Сложность. Без реаллокации — O(1). В худшем случае одна вставка стоит O(n): нужно скопировать n элементов. Амортизированно при удвоении — O(1): суммарные копии за m вставок меньше 2m, значит суммарная стоимость меньше 3m, а средняя — меньше 3. Память O(1) дополнительно (кроме самого буфера).

Крайние случаи. Пустой массив: начальная ёмкость 1 или сразу reserve. Очень большой n: 2c может переполнить size_t — нужна проверка c > max/2. Если перенос элемента бросает исключение, нужна аккуратная гарантия безопасности; учебная реализация ниже упрощена.

Рисунок. См. рис. 2.

Операция: вставка в позицию (`insert`)

Идея. Сдвинуть элементы data[i..n−1] на один вправо, освободив позицию i, и записать новый элемент. Если буфер полон, сначала увеличить ёмкость.

Шаги.

Проверить 0 ≤ i ≤ n.
Если n = c, выполнить реаллокацию (как в push_back).
Для j от n до i + 1: data[j] ← data[j−1].
data[i] ← x; n ← n + 1.

Инвариант. После сдвига элементы data[0..n] упорядочены по индексам, позиция i свободна; после записи размер увеличился на 1.

Псевдокод.

Алгоритм Insert(A, i, x)
Вход:  A — динамический массив; i — позиция; x — элемент
Выход: A с x в позиции i
Инвариант: 0 ≤ i ≤ A.n ≤ A.c

1  if i < 0 or i > A.n
2      error "позиция вне диапазона"
3  if A.n = A.c
4      Reallocate(A, max(1, 2·A.c))
5  for j ← A.n downto i + 1
6      A.data[j] ← A.data[j − 1]
7  A.data[i] ← x
8  A.n ← A.n + 1

Сложность: O(n) времени, O(1) дополнительной памяти.
Корректность: сдвиг сохраняет порядок; x встаёт на освобождённое место.

Пример. В массиве [10, 20, 30, 40, 50] вставим 25 в позицию 2. Сдвигаются 50, 40, 30 (в обратном порядке), затем 25 записывается в позицию 2; получается [10, 20, 25, 30, 40, 50] (рис. 4).

Рис. 4. Вставка 25 в позицию 2: элементы 30, 40, 50 сдвигаются вправо, затем 25 записывается на место.

Сложность. В худшем случае O(n): сдвигаются все n − i элементов. В лучшем (i = n) — O(1) амортизированно, как push_back. Память O(1).

Крайние случаи. i = 0 — сдвиг всего массива; i = n — добавление в конец; i вне [0, n] — ошибка. При полном буфере реаллокация добавляет O(n) к стоимости, но не меняет асимптотику.

Рисунок. См. рис. 4.

Операция: удаление (`erase`, `pop_back`)

Идея. pop_back удаляет последний элемент за O(1). erase(i) сдвигает элементы data[i+1..n−1] на один влево и уменьшает n. При сильном опустошении ёмкость можно уменьшить.

Шаги erase(i).

Проверить 0 ≤ i < n.
Для j от i до n − 2: data[j] ← data[j+1].
n ← n − 1.
Если c > 4 и n < c/4, уменьшить ёмкость до c/2 (сжатие).

Инвариант. После сдвига элементы data[0..n−2] сохраняют порядок; размер уменьшился на 1; при сжатии n ≤ c сохраняется.

Псевдокод.

Алгоритм Erase(A, i)
Вход:  A — динамический массив; i — индекс
Выход: A без элемента i
Инвариант: 0 ≤ i < A.n ≤ A.c

1  if i < 0 or i ≥ A.n
2      error "индекс вне диапазона"
3  for j ← i to A.n − 2
4      A.data[j] ← A.data[j + 1]
5  A.n ← A.n − 1
6  if A.c > 4 and A.n < A.c / 4
7      Reallocate(A, A.c / 2)             # гистерезис: не при n = c/2

Сложность: O(n) для erase; pop_back без сжатия — O(1), при сжатии — O(n); сжатие амортизированно O(1).
Корректность: сдвиг влево сохраняет порядок; сжатие не отбрасывает элементы.

Пример. Из [10, 20, 25, 30, 40, 50] удалим 25 (индекс 2): 30, 40, 50 сдвигаются влево, получается [10, 20, 30, 40, 50]. pop_back на исходном массиве из шести элементов уменьшает n с 6 до 5.

Сложность. erase — O(n). pop_back без сжатия — O(1), но при n < c/4 он вызывает сжатие и стоит O(n). Сжатие происходит после не менее c/4 удалений, поэтому амортизированно O(1).

Крайние случаи. Удаление из пустого массива — ошибка. Удаление последнего элемента — pop_back. Если после сжатия снова добавить элементы, гистерезис не даёт немедленно расширяться и сжиматься на каждой операции.

Рисунок. См. рис. 6.

Операция: `reserve` и `shrink_to_fit`

Идея. reserve(c) заранее выделяет ёмкость, чтобы избежать реаллокаций в цикле. shrink_to_fit() пытается освободить лишнюю память, уменьшая ёмкость до размера.

Шаги. reserve: если c > capacity, реаллоцировать в c; иначе ничего не делать. shrink_to_fit: если size < capacity, реаллоцировать в size (или меньшее значение, достаточное для элементов).

Инвариант. size ≤ capacity; элементы не меняются; порядок сохраняется.

Псевдокод.

Алгоритм Reserve(A, c)
1  if c > A.c
2      Reallocate(A, c)

Алгоритм Shrink-To-Fit(A)
1  if A.n < A.c
2      Reallocate(A, max(A.n, 1))

Сложность: O(n) времени на копирование; память O(c) для reserve(c) и O(n) для shrink_to_fit; это одна операция, а не амортизированная на элемент.
Корректность: реаллокация переносит все элементы без изменения порядка.

Пример. Если известно, что будет 1000 вставок, reserve(1000) избавит от реаллокаций на 1, 2, 4, …, 512. После удаления 900 элементов shrink_to_fit() вернёт память, но следующая серия вставок снова начнёт расти.

Сложность. reserve(c) — O(n) на копирование и O(c) памяти; shrink_to_fit — O(n) времени и O(n) памяти. Обе не меняют амортизированную стоимость push_back.

Крайние случаи. reserve меньше текущей ёмкости не уменьшает её (по стандарту std::vector). shrink_to_fit не гарантирует уменьшение: реализация вправе оставить ёмкость. reserve с огромным c может бросить bad_alloc.

Рисунок. См. рис. 1 и рис. 6.

Операция: поиск

Идея. В неупорядоченном массиве — линейный поиск; в отсортированном — двоичный.

Шаги. Линейный: перебрать data[0..n−1]; двоичный: поддерживать lo, hi и сравнивать с data[mid].

Инвариант. Линейный: все элементы до i проверены. Двоичный: если ключ есть, он в data[lo..hi].

Псевдокод.

Алгоритм Linear-Search(A, x)
1  for i ← 0 to A.n − 1
2      if A.data[i] = x  return i
3  return NIL

Сложность: O(n) времени, O(1) памяти.
Корректность: перебираются все элементы.

Пример. В [10, 20, 30, 40, 50] поиск 40 делает четыре сравнения (индексы 0–3).

Сложность. Линейный — O(n); двоичный — O(log n) сравнений, но требует отсортированности и не ускоряет вставку.

Крайние случаи. Пустой массив — NIL. Дубликаты — линейный поиск возвращает первый найденный; для множества дубликаты обычно запрещают.

Рисунок. См. рис. 1.

Сводная таблица сложности

Операция	Худшее	Среднее	Амортизированное	Память
Доступ `A[i]`	`O(1)`	`O(1)`	`O(1)`	`O(1)`
`push_back`	`O(n)`	`O(1)`	`O(1)`	`O(1)`
`pop_back`	`O(n)` при сжатии, иначе `O(1)`	`O(1)`	`O(1)`	`O(1)`
`insert(i)`	`O(n)`	`O(n)`	`O(n)`	`O(1)`
`erase(i)`	`O(n)`	`O(n)`	`O(n)`	`O(1)`
Поиск (неупоряд.)	`O(n)`	`O(n)`	`O(n)`	`O(1)`
Поиск (сортированный)	`O(log n)`	`O(log n)`	`O(log n)`	`O(1)`
`reserve(c)`	`O(n)`	`O(n)`	—	`O(c)`
`shrink_to_fit`	`O(n)`	`O(n)`	—	`O(n)`
Память контейнера	—	—	—	`c` слотов

Примечание. Амортизированная оценка push_back верна для геометрического роста. При c ← c + 1 она превращается в Θ(n), а при c ← c + k — в Θ(n/k). Худший случай одной вставки всегда O(n) из-за копирования.

Трассировка примера

Начнём с пустого массива и будем добавлять 10, 20, 30, 40, 50. Ёмкость удваивается: 1, 2, 4, 8.

Шаг	Операция	`n`	`c`	Буфер	Копий
0	старт	0	0	`[]`	0
1	push 10	1	1	`[10]`	0
2	push 20	2	2	`[10, 20]`	1
3	push 30	3	4	`[10, 20, 30, _]`	2
4	push 40	4	4	`[10, 20, 30, 40]`	0
5	push 50	5	8	`[10, 20, 30, 40, 50, _, _, _]`	4

Суммарно скопировано 1 + 2 + 4 = 7 элементов при пяти вставках. Если бы рост был +1, копий было бы 0 + 1 + 2 + 3 + 4 = 10, а при больших m разрыв стал бы квадратичным. После вставки 25 в позицию 2 буфер станет [10, 20, 25, 30, 40, 50, _, _]; n = 6, c = 8. После pop_back — n = 5, c = 8; сжатие при n < c/4 = 2 пока не срабатывает.

Корректность и оценка сложности

Лемма 1 (инвариант размера). После каждой операции 0 ≤ n ≤ c, а элементы data[0..n−1] идут в порядке индексов.

Доказательство. Индукция по операциям. Начальное состояние n = c = 0 допустимо. push_back либо пишет в свободный слот (n < c), либо предварительно увеличивает c до 2c при c > 0 (при c = 0 — до 1), после чего n < c; запись увеличивает n на 1. insert сначала обеспечивает n < c, затем сдвигает элементы и увеличивает n. erase уменьшает n; сжатие выбирает c' = c/2 > n, так как n < c/4. Порядок сохраняется сдвигом на одну позицию. [math]\displaystyle{ \blacksquare }[/math]

Теорема 2 (амортизированная стоимость удвоения). При c ← 2c и m операциях push_back суммарная стоимость O(m), амортизированная — O(1).

Доказательство (агрегатный метод). Каждая вставка стоит 1 за запись. Копирования происходят, когда размер достигает 1, 2, 4, …; суммарно копируется 1 + 2 + 4 + … + 2^{k} < 2m элементов, где 2^{k} < m. Итого T(m) ≤ m + 2m = 3m, значит T(m)/m ≤ 3 = O(1). [math]\displaystyle{ \blacksquare }[/math]

Теорема 3 (потенциал удвоения). Для Φ = 2n − c (при c ≥ 0) амортизированная стоимость push_back не превосходит 3.

Доказательство. Без реаллокации: n' = n + 1, c' = c, ΔΦ = 2, фактическая стоимость 1, амортизированная 1 + 2 = 3. При реаллокации n = c, c' = 2c, n' = c + 1; Φ = c, Φ' = 2(c + 1) − 2c = 2, ΔΦ = 2 − c; фактическая стоимость c + 1 (копирование и запись), амортизированная c + 1 + 2 − c = 3. Первая вставка при c = 0: Φ = 0, Φ' = 1, ΔΦ = 1, стоимость 1, амортизированная 2. Во всех случаях не больше 3. Схема потенциала и кредитов — на рис. 5. [math]\displaystyle{ \blacksquare }[/math]

Рис. 5. Потенциал Φ = 2n − c: фактические затраты скачут на реаллокациях, а амортизированные остаются не больше 3.

Рис. 6. Гистерезис сжатия: порог c/4 и уменьшение до c/2 не дают буферу расширяться и сжиматься на каждой операции.

Теорема 4 (арифметический рост). При c ← c + k суммарная стоимость m вставок есть Θ(m²/k), амортизированная — Θ(m/k).

Доказательство. Реаллокации происходят на размерах k, 2k, 3k, …; копируется k + 2k + … + (m/k)k = k·(1 + 2 + … + m/k) = Θ(m²/k). Деление на m даёт Θ(m/k). При фиксированном k это Θ(m), то есть Θ(n) на операцию. [math]\displaystyle{ \blacksquare }[/math]

Сжатие и гистерезис. Если уменьшать ёмкость при n ≤ c/2 до c/2, то после сжатия буфер почти полон: через несколько вставок происходит рост, а следующее удаление снова сжимает. Чередование push_back и pop_back на границе вызывает реаллокацию почти на каждой операции. Порог n < c/4 с уменьшением до c/2 оставляет зазор: после сжатия c/2 > 2n, и нужно не менее c/4 вставок, чтобы снова заполнить буфер. Поэтому сжатие амортизированно O(1): стоимость O(c) раскладывается на Ω(c) операций.

Память. При геометрическом росте c ≤ αn (с точностью до начального значения), поэтому запас не больше (α−1)n. При удвоении в момент реаллокации одновременно живы старый и новый буферы: до n + 2n = 3n слотов; после освобождения старого — 2n. reserve убирает повторные реаллокации, но может увеличить запас.

Сравнение с альтернативами

Структура	Доступ	Вставка в конец	Вставка в середину	Память	Локальность
Динамический массив	`O(1)`	`O(1)` аморт.	`O(n)`	`c` слотов; обычно `c ≤ αn`, после `reserve` — больше	отличная
Связный список	`O(n)`	`O(1)`	`O(1)` при известном узле	`O(n)` + указатели	плохая
Дека (deque)	`O(1)`	`O(1)`	`O(n)`	блоки	хорошая
Фиксированный массив	`O(1)`	—	`O(n)`	ровно `n`	отличная
Rope / дерево строк	`O(log n)`	`O(log n)`	`O(log n)`	`O(n)`	средняя

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

Сводное сравнение — на рис. 7.

Рис. 7. Динамический массив выигрывает на доступе и обходе; связный список — на вставках в известную позицию; дека — на операциях с двух концов.

Где применяется

std::vector в C++. Стандартный последовательный контейнер; push_back использует геометрический рост, а reserve заранее выделяет ёмкость; непрерывный буфер даёт совместимость с C-массивами [3].
ArrayList в Java. Обёртка над динамическим массивом; рост ёмкости и копирование скрыты от пользователя, доступ по индексу — O(1) [6].
list в Python. Список CPython хранит массив указателей на объекты и использует over-allocation; append амортизированно O(1), доступ по индексу O(1) [5].
Vec в Rust. Непрерывный буфер с явными capacity, reserve и проверкой границ; владение и заимствование делают реаллокацию видимой в типах [4].
Буферы парсеров, компиляторов и сетевых стеков. Строки, токены и пакеты часто накапливаются в динамическом массиве: важен быстрый последовательный обход и амортизированная вставка в конец.

Историческая справка

1970–1980-е. Массивы с изменяемым размером используются в языках и библиотеках. Позднее анализ амортизированной стоимости динамических таблиц систематизирован в CLRS (1990; 3-е изд. 2009), гл. 17 [1].
1990-е. В STL C++ появляется std::vector; контейнер стандартизирован в C++98 и остаётся основным последовательным контейнером [3].
1998. Java Collections Framework включает ArrayList, наследующий идею динамического массива [6].
2000-е–наст. Динамические массивы — базовый контейнер в Python, Rust, Go, Swift; обсуждаются коэффициенты роста, reserve, сжатие и безопасность памяти.

Типичные ошибки и подводные камни

Рост на +1. Даёт Θ(n²) суммарно; всегда используйте геометрический рост или reserve.
Сжатие при n = c/2. Приводит к дребезгу при чередовании вставок и удалений; используйте гистерезис (n < c/4 → c/2).
Сохранение указателей и итераторов после реаллокации. При реаллокации все ссылки, указатели и итераторы на элементы инвалидируются; без реаллокации после push_back инвалидируется только end(). Поэтому после роста их нужно получать заново.
reserve вместо изменения размера. reserve не добавляет элементы; resize добавляет, reserve только меняет ёмкость.
Ожидание shrink_to_fit. Стандарт не гарантирует уменьшение ёмкости; это необязывающий запрос.
Переполнение при удвоении. 2c может не поместиться в size_t; проверяйте c > max/2.
std::vector<bool>. Специализация хранит биты, а не bool-объекты; data() и ссылки ведут себя иначе.
Исключения при копировании. При реаллокации перенос может бросить исключение; production-реализации используют аллокаторы и аккуратные гарантии.
Путаница размера и ёмкости. size() — число элементов, capacity() — слотов; size ≤ capacity всегда.

Задачи для практики

Реализация. Реализуйте push_back, insert, erase, reserve и shrink_to_fit для int. Ограничения: не использовать std::vector. Подсказка: проверяйте size == capacity до записи.
Амортизация. Докажите, что при α = 1.5 суммарное число копий за m вставок есть O(m), и оцените константу. Подсказка: геометрическая прогрессия со знаменателем 1/1.5.
Арифметический рост. Постройте последовательность из 1000 вставок при c ← c + 10 и посчитайте копии. Сравните с удвоением. Подсказка: 10·(1+2+…+99).
Сжатие. Реализуйте сжатие с порогом c/4 и проверьте, что чередование push_back/pop_back не вызывает реаллокацию на каждой паре. Подсказка: после сжатия c/2 > 2n.
Вставка в середину. Оцените число сдвигов при вставке в позицию i и найдите среднее по всем i. Подсказка: (n−i) сдвигов.
Поиск. Сравните линейный поиск в динамическом массиве и поиск в связном списке по времени и кэшу. Подсказка: непрерывный буфер читается блоками.
reserve. Для n = 10^6 сравните число реаллокаций при reserve(n) и без него. Подсказка: без reserve — около log₂ n реаллокаций.
Безопасность. Обсудите, какие операции инвалидируют итераторы std::vector и почему reserve может инвалидировать все итераторы сразу.

Ответы (кратко). 1. См. реализацию ниже. 2. Копии ≤ αm/(α−1), для α=1.5 — ≤3m. 3. 10·(1+…+99)=49500 копий против <2000 при удвоении. 4. После сжатия запас c/2−n > c/4, поэтому нужно много вставок. 5. В среднем n/2 сдвигов, O(n). 6. Массив быстрее за счёт локальности. 7. Около 20 реаллокаций против 0. 8. Реаллокация инвалидирует все; insert/erase — итераторы в позиции и после неё.

Реализация на C++

Учебная реализация DynamicArray с удвоением, reserve, insert, erase и сжатием. Она упрощена: не использует аллокатор и не даёт сильной гарантии исключений; для production-кода берите std::vector.

#include <cassert>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <utility>

template <class T>
class DynamicArray {
    T* data_ = nullptr;
    std::size_t size_ = 0;
    std::size_t cap_ = 0;

    void reallocate(std::size_t newCap) {
        T* p = new T[newCap];
        for (std::size_t i = 0; i < size_; ++i)
            p[i] = std::move(data_[i]);
        delete[] data_;
        data_ = p;
        cap_ = newCap;
    }

public:
    DynamicArray() = default;
    ~DynamicArray() { delete[] data_; }
    DynamicArray(const DynamicArray&) = delete;
    DynamicArray& operator=(const DynamicArray&) = delete;

    std::size_t size() const { return size_; }
    std::size_t capacity() const { return cap_; }
    bool empty() const { return size_ == 0; }

    T& operator[](std::size_t i) {
        if (i >= size_) throw std::out_of_range("index");
        return data_[i];
    }
    const T& operator[](std::size_t i) const {
        if (i >= size_) throw std::out_of_range("index");
        return data_[i];
    }

    void reserve(std::size_t c) {
        if (c > cap_) reallocate(c);
    }

    void push_back(const T& x) {
        if (size_ == cap_) reallocate(cap_ ? cap_ * 2 : 1);
        data_[size_++] = x;
    }

    void insert(std::size_t i, const T& x) {
        if (i > size_) throw std::out_of_range("insert");
        if (size_ == cap_) reallocate(cap_ ? cap_ * 2 : 1);
        for (std::size_t j = size_; j > i; --j)
            data_[j] = std::move(data_[j - 1]);
        data_[i] = x;
        ++size_;
    }

    void erase(std::size_t i) {
        if (i >= size_) throw std::out_of_range("erase");
        for (std::size_t j = i; j + 1 < size_; ++j)
            data_[j] = std::move(data_[j + 1]);
        --size_;
        if (cap_ > 4 && size_ < cap_ / 4) reallocate(cap_ / 2);
    }

    void pop_back() {
        if (size_ == 0) throw std::out_of_range("pop_back");
        --size_;
        if (cap_ > 4 && size_ < cap_ / 4) reallocate(cap_ / 2);
    }

    void shrink_to_fit() {
        if (size_ < cap_) reallocate(size_ ? size_ : 1);
    }
};

int main() {
    DynamicArray<int> a;
    for (int i = 1; i <= 100; ++i) a.push_back(i);
    assert(a.size() == 100);
    assert(a.capacity() >= 100);

    a.insert(0, 0);              // [0, 1, ..., 100]
    assert(a[0] == 0 && a[1] == 1 && a[100] == 100);
    a.erase(0);
    assert(a[0] == 1 && a.size() == 100);

    a.reserve(1000);
    assert(a.capacity() >= 1000);
    for (int i = 0; i < 90; ++i) a.pop_back();
    a.shrink_to_fit();
    assert(a.size() == 10 && a.capacity() >= 10);

    DynamicArray<int> b;
    b.push_back(1);
    b.push_back(2);
    b.insert(1, 3);              // полная ёмкость: реаллокация и сдвиг
    assert(b.size() == 3 && b[1] == 3 && b[2] == 2);
    b.erase(1);
    assert(b.size() == 2 && b[1] == 2);
    b.reserve(1);                // меньше текущей ёмкости: не уменьшает
    assert(b.capacity() >= 2);

    std::cout << "ok\n";
    return 0;
}

Замечания по реализации.

reallocate копирует/перемещает элементы в том же порядке; старый буфер освобождается.
Удвоение даёт амортизированное O(1); reserve убирает повторные реаллокации.
Сжатие срабатывает только при size < capacity/4; порог capacity/2 дал бы дребезг.
Класс запрещает копирование, чтобы не было двойного delete[]; в учебных целях можно добавить конструктор копирования.
Для типов с исключениями при перемещении нужна более аккуратная реализация.

Связанные темы

амортизационный-анализ — агрегатный метод, метод предоплаты и потенциала.
асимптотическая-сложность — O, Ω, Θ и логарифмы.
двоичная-куча — массив, используемый как двоичное дерево.
сортировки — массивы как основа сортировок.
связный-список (план) — альтернатива с указателями.
дека (план) — очередь с двумя концами.

Источники

Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 17 «Amortized Analysis», §17.4 «Dynamic tables».
Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — §1.3 (resizing arrays), §1.4 (amortized analysis).
cppreference.com: std::vector. URL: https://en.cppreference.com/w/cpp/container/vector.
Wikipedia: Dynamic array. URL: https://en.wikipedia.org/wiki/Dynamic_array.
Python Documentation: Data Structures. URL: https://docs.python.org/3/tutorial/datastructures.html.
Oracle Java Documentation: ArrayList. URL: https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html.

Поиск

Навигация

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

Содержание

TL;DR

Определения

Мотивация и интуиция

Устройство

Операции и алгоритмы

Операция: доступ и изменение по индексу

Операция: вставка в конец (`push_back`)

Операция: вставка в позицию (`insert`)

Операция: удаление (`erase`, `pop_back`)

Операция: `reserve` и `shrink_to_fit`

Операция: поиск

Сводная таблица сложности

Трассировка примера

Корректность и оценка сложности

Сравнение с альтернативами

Где применяется

Историческая справка

Типичные ошибки и подводные камни

Задачи для практики

Реализация на C++

Связанные темы

Источники

Навигация

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

TL;DR

Определения

Мотивация и интуиция

Устройство

Операции и алгоритмы

Операция: доступ и изменение по индексу

Операция: вставка в конец (push_back)

Операция: вставка в позицию (insert)

Операция: удаление (erase, pop_back)

Операция: reserve и shrink_to_fit

Операция: поиск

Сводная таблица сложности

Трассировка примера

Корректность и оценка сложности

Сравнение с альтернативами

Где применяется

Историческая справка

Типичные ошибки и подводные камни

Задачи для практики

Реализация на C++

Связанные темы

Источники

Операция: вставка в конец (`push_back`)

Операция: вставка в позицию (`insert`)

Операция: удаление (`erase`, `pop_back`)

Операция: `reserve` и `shrink_to_fit`