В чем проблема при вставке 100 элементов в конец std::vector без подготовки?

Основная проблема — множественные реаллокации, которые приводят к падению производительности.

Механизм работы std::vector:

1. Вектор хранит элементы в непрерывном блоке памяти.
2. У него есть два размера: size() (количество элементов) и capacity() (размер выделенного блока памяти).
3. При push_back(), если size() == capacity(), происходит реаллокация: выделяется новый, больший блок памяти (обычно в 1.5 или 2 раза больше), все существующие элементы копируются или перемещаются в него, старый блок освобождается.

Пример с проблемой:

std::vector<int> vec; // capacity = 0
for (int i = 0; i < 100; ++i) {
    vec.push_back(i); // Реаллокации произойдут при i = 0, 1, 2, 4, 8, 16, 32, 64...
}
// Каждая реаллокация — это O(N) операций копирования/перемещения.

Решение — метод reserve():

std::vector<int> vec;
vec.reserve(100); // Однократное выделение памяти под 100 элементов
for (int i = 0; i < 100; ++i) {
    vec.push_back(i); // Ни одной реаллокации. Вставка за O(1).
}

Дополнительные соображения:

• Использование emplace_back() вместо push_back() позволяет конструировать объекты прямо в памяти вектора, избегая лишних копирований.
• Если конечный размер известен, можно использовать конструктор или assign().

  // Альтернатива: инициализация из итераторов или списка
  std::vector<int> vec(100); // 100 элементов, инициализированных нулями
  // или
  std::vector<int> vec;
  vec.assign(100, 0); // 100 нулей