Как растёт vector
Вопрос
Расскажите, как устроен std::vector, что происходит при push_back в заполненный вектор и какие последствия это имеет для итераторов и производительности.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Три указателя: начало, конец данных, конец ёмкости
Геометрический рост ёмкости, амортизированное O(1)
Реаллокация: новый буфер, перенос элементов, освобождение старого
Перемещение при реаллокации только если noexcept
Инвалидация всех итераторов, указателей и ссылок
reserve, если размер известен заранее
Что могут спросить следом
- Почему рост в 1,5 раза, а не в 2 раза, может быть выгоднее?
- Что будет с указателем на элемент после insert в начало?
Разбор
Вектор хранит указатель на начало буфера, указатель на конец данных и на конец выделенной памяти. Пока ёмкости хватает, push_back просто конструирует элемент в конце. Если ёмкость кончилась, выделяется новый буфер большего размера: libstdc++ и libc++ удваивают, MSVC растит в полтора раза. Элементы переносятся в новый буфер: перемещением, если перемещающий конструктор noexcept, иначе копированием, затем старые уничтожаются и память освобождается. Благодаря геометрическому росту суммарная работа на n вставок линейная, и push_back стоит амортизированно O(1). Последствие: после реаллокации все итераторы, указатели и ссылки на элементы висят, их нельзя хранить через вставки. Если размер известен заранее, делаю reserve: меньше аллокаций и копирований. А удаление из середины сдвигает хвост и тоже инвалидирует итераторы с этой позиции.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.