I am reading C Primer on vector push_back() and trying to understand the below statement.

Every implementation is required to follow a strategy that ensures that it is efficient to use push_back to add elements to a vector. Technically speaking, the execution time of creating an n-element vector by calling push_back n times on an initially empty vector must never be more than a constant multiple of n

I have read quite a bit of data structure on this but just do not understand the one in BOLD ITALIC. Not sure what the author is trying to say especially the word "MULTIPLE".

Wondering as an example if n=5 does the author meant multiple of 5 (e.g. 5 or 10 or 15 etc)?

Appreciate any help.

CodePudding user response：

The author is saying that there must exist a constant value c, such that inserting n elements into the vector does never take longer than c*n.

For example that c could be for a given element type one microsecond per item. In that case inserting 100 items into the vector will not take longer than 100 microseconds.

Technically that isn't exactly the guarantee you have. There is usually no obvious way to precisely define such a time bounds on real systems. And if the time required in the constructors of the element type is not constant, it may also impact this kind of time guarantee.

Instead the standard makes such a guarantee only about the number of times that an operation will be performed on the elements. So here for example if the vector's element type is a class type, c could be 3 per element, which would mean that inserting 100 elements will at most call constructors of the element type 300 times.

This is meant as an asymptotic bound and not to determine actual time execution takes for small values of n.

This requirement is also known as amortized constant time complexity for individual push_back.