Как устроен динамический массив и что происходит при ресайзе?

Динамический массив — это обычный массив с запасом ёмкости: при переполнении выделяется новый буфер примерно вдвое больше, элементы копируются, поэтому push работает амортизированно за O(1).

Устройство

• size — сколько элементов логически, capacity — сколько влезает физически.
• Пока size < capacity, вставка в конец — простая запись за O(1).

Ресайз

• При переполнении: новый буфер ёмкостью 2×capacity и копирование всех элементов за O(n).
• Редкие копирования размазываются: на n вставок суммарно O(n) работы, в среднем O(1) на операцию — это амортизированный анализ.
• Коэффициент роста 1.5–2 — компромисс между памятью и числом копирований.

Что нужно знать

• Ссылки и итераторы на элементы инвалидируются при ресайзе.
• Уменьшение буфера делают с запасом (например, при заполнении меньше четверти), чтобы capacity не дребезжала на границе.

Коротко для собеседования

Динамический массив держит запас ёмкости и при переполнении перевыделяет буфер с геометрическим ростом, поэтому дорогие копирования редки и push в среднем стоит O(1). Растить нужно в разы, а не на фиксированное число элементов, иначе суммарное копирование станет квадратичным; и помните, что после ресайза старые ссылки на элементы недействительны.