Какой временной эффект ожидается при добавлении элементов в std::vector?

Добавление элементов в std::vector обычно имеет амортизированную константную временную сложность — O(1) в среднем. Это связано с тем, что вектор выделяет память с запасом, и при добавлении новых элементов, если текущий буфер не заполнен, элемент просто помещается в конец.

Однако, когда выделенной памяти не хватает, происходит операция перераспределения (reallocation): выделяется новый блок памяти большего размера, все существующие элементы копируются или перемещаются в новый буфер, а старый освобождается. Эта операция занимает O(n) времени, где n — текущее количество элементов.

Таким образом, в среднем добавление элемента — O(1), но иногда — O(n). Это называется амортизированной константной сложностью.

Пример:

std::vector<int> v;
for (int i = 0; i < 1000; ++i) {
    v.push_back(i); // Обычно O(1), иногда O(n) при перераспределении
}