What is the expected time effect when adding elements to std::vector?

Adding elements to std::vector typically has amortized constant time complexity — O(1) on average. This is because the vector allocates extra memory, and when new elements are added, if the current buffer is not full, the element is simply placed at the end.

However, when there is not enough allocated memory, a reallocation occurs: a new, larger memory block is allocated, all existing elements are copied or moved to the new buffer, and the old one is freed. This operation takes O(n) time, where n is the current number of elements.

Thus, on average, adding an element is O(1), but sometimes it is O(n). This is called amortized constant complexity.

Example:

std::vector<int> v;
for (int i = 0; i < 1000; ++i) {
    v.push_back(i); // Usually O(1), sometimes O(n) during reallocation
}