Всегда ли объект добавляется в вектор за константное время?

Ответ: О(1) амортизированное время, но не всегда константное

Вопрос затрагивает важное различие между амортизированной и гарантированной сложностью. Ответ: НЕТ, не всегда, хотя амортизированно это O(1).

Как работает std::vector::push_back()

std::vector использует динамическое расширение буфера:

std::vector<int> v;
v.push_back(1);  // O(1) — есть место в буфере
v.push_back(2);  // O(1) — есть место в буфере
v.push_back(3);  // O(n) — буфер переполнен, выделяем новый
                 // копируем все элементы туда

Когда происходит перевыделение памяти

Когда size() == capacity(), вектор:

1. Выделяет новый буфер большего размера (обычно в 1.5-2 раза)
2. Копирует все элементы в новый буфер: O(n)
3. Освобождает старый буфер
4. Добавляет новый элемент: O(1)

std::vector<int> v;
std::cout << v.capacity() << std::endl;  // 0

for (int i = 0; i < 10; ++i) {
    std::cout << "Before: size=" << v.size() 
              << ", capacity=" << v.capacity() << std::endl;
    v.push_back(i);
    std::cout << "After: size=" << v.size() 
              << ", capacity=" << v.capacity() << std::endl;
}

Вывод покажет скачки capacity: 0→1→2→4→8→16...

Амортизированная сложность O(1)

Хотя отдельное добавление может быть O(n), если рассматривать n добавлений:

1 + 1 + 1 + n/2 + 1 + ... + 1 + n/4 + ... = O(n)

Время на одно добавление в среднем: O(n) / n = O(1) амортизированно

Это значит: N последовательных push_back() займут O(N) времени в целом.

Практические следствия

Избежать переаллокаций:

std::vector<int> v;
v.reserve(1000);  // Выделяем сразу нужный размер

for (int i = 0; i < 1000; ++i) {
    v.push_back(i);  // Теперь всегда O(1)
}

В критичном коде:

// ❌ Опасно — может быть гарантированно O(n)
for (int i = 0; i < MILLION; ++i) {
    data.push_back(processItem());  // Если переаллокация совпадёт с критичным моментом
}

// ✅ Безопаснее
data.reserve(MILLION);
for (int i = 0; i < MILLION; ++i) {
    data.push_back(processItem());
}

Итог

✅ Амортизированная сложность: O(1) для любого количества добавлений ✅ Гарантированная сложность отдельной операции: O(n) в худшем случае (при переаллокации) ✅ Решение: используй reserve() если нужна гарантия O(1)