does std::vector::insert allocate spare capacity?

Question

Code like

std::vector<int> a;
for(size_t i = 0; i < n; ++i)
    a.push_back(0);

is guaranteed to run in linear time in n. This is achieved by allocating some additional spare capacity when reallocating (typically increasing the total capacity by a constant factor).

But what about std::vector::insert(pos, x)? I.e. is it guaranteed that

std::vector<int> a;
for(size_t i = 0; i < n; ++i)
    a.insert(a.end(), 0);

is linear as well? (similar question applies to insert(pos, first, last) of course)

The documentaiton of push_back is clear in guaranteeing "amortized constant" complexity.

But the documentation of insert says the complexity should be "constant plus linear in the distance between pos and end of the container". This can obviously only be true if no reallocation happens, thus my uncertainty.

EDIT: Summary of the answers: When a reallocation occurs, the implementation can either

1. increase the capacity the bare minimum
2. or increase the capacity more than the minimum, thus making future insertions faster.

In the case of push_back, option (2) is essentially required to achieve the "amortized constant" runtime. In the case of insert(pos, first, last), option (2) is required in case of single-pass InputIterator (But in case of multi-pass ForwardIterator, the implementation can and does use a single reallocation with new_capacity = max(2*old_capacity, new_size)). All other cases are implementation defined.

Testing with GCC 11 and clang 12, the situation seems to be:

1. reserve and assign increase capacity by the bare minimum, and
2. push_back and insert and resize increase the capacity by a constant factor

Answer 1

"Amortized constant" means "constant most of the time". push_back will be O(1) for most of the calls. If reallocation is required, it will be linear, but this should happen relatively rarely.

If reallocation is required for insert, all elements will be moved, that's O(n). If reallocation is not required, all the elements to the right of newly inserted elements are moved, but that's still O(n).

---

Cppreference doesn't seem to mention reallocation in Complexity section reliably. For example, resize() mentions possible additional complexity in Complexity section, but push_back() and insert() mention reallocation only in the function description. Might be worth to clean it up one day.