Всегда ли добавление элемента в `std::vector` происходит за константное время O(1)?

Нет, не всегда. Сложность операции push_back() — амортизированная константная O(1), но не чистая константная.

Механизм работы и сложность:

• O(1): Если в векторе есть свободная емкость (size() < capacity()), push_back просто размещает элемент в конце — это константная операция.
• O(N): Если вектор заполнен (size() == capacity()), происходит реаллокация (reallocation). Алгоритм выделяет новый блок памяти, обычно в 1.5 или 2 раза больше предыдущего, перемещает (или копирует) все существующие элементы в новый блок, а затем добавляет новый элемент. Перемещение всех N элементов имеет линейную сложность.

Пример, демонстрирующий разницу:

#include <vector>
#include <iostream>
#include <chrono>

int main() {
    std::vector<int> v;
    v.reserve(5); // Устанавливаем capacity = 5

    // Эти 5 вызовов будут выполняться за O(1) каждый
    for (int i = 0; i < 5; ++i) {
        v.push_back(i); // Без реаллокаций
    }

    // Этот вызов вызовет реаллокацию (capacity станет, например, 10)
    // Все 5 старых элементов будут перемещены, сложность O(N)
    v.push_back(5);

    std::cout << "Size: " << v.size() << std::endl;     // 6
    std::cout << "Capacity: " << v.capacity() << std::endl; // 10
    return 0;
}

Практический вывод: Для предсказуемой производительности, когда известно примерное количество элементов, следует использовать метод reserve(). Это позволяет избежать множественных реаллокаций и обеспечивает истинно константное время добавления в пределах зарезервированной емкости.