Does std::vector::insert reserve by definition?

Question

When calling the insert member function on a std::vector, will it reserve before "pushing back" the new items? I mean does the standard guarantee that or not?

In other words, should I do it like this:

std::vector<int> a{1,2,3,4,5};
std::vector<int> b{6,7,8,9,10};
a.insert(a.end(),b.begin(),b.end());

or like this:

std::vector<int> a{1,2,3,4,5};
std::vector<int> b{6,7,8,9,10};
a.reserve(a.size()+b.size());
a.insert(a.end(),b.begin(),b.end());

or another better approach?

Answer 1

Regarding the complexity of the function [link]:

Linear on the number of elements inserted (copy/move construction) plus the number of elements after position (moving).

Additionally, if InputIterator in the range insert (3) is not at least of a forward iterator category (i.e., just an input iterator) the new capacity cannot be determined beforehand and the insertion incurs in additional logarithmic complexity in size (reallocations).

Hence, there is two cases :

• The new capacity can be determined, therefore you won't need to call reserve
• The new capacity can't be determined, hence a call to reserve should be useful.

Answer 2

Does std::vector::insert reserve by definition?

Not always; depends on the current capacity.

From the draft N4567, §23.3.6.5/1 ([vector.modifiers]):

Causes reallocation if the new size is greater than the old capacity.

If the allocated memory capacity in the vector is large enough to contain the new elements, no additional allocations for the vector are needed. So no, then it won't reserve memory.

If the vector capacity is not large enough, then a new block is allocated, the current contents moved/copied over and the new elements are inserted. The exact allocation algorithm is not specified, but typically it would be as used in the reserve() method.

... or another better approach?

If you are concerned about too many allocations whilst inserting elements into the vector, then calling the reserve method with the size of the number of expected elements to be added does minimise the allocations.

Does the vector call reserve before the/any insertions? I.e. does it allocate enough capacity in a single allocation?

No guarantees. How would it know the distance between the to input iterators? Given that the insert method can take an InputIterator (i.e. single pass iterator), it has no way of calculating the expected size. Could the method calculate the size if the iterators where something else (e.g. pointers or RandomAccessIterator)? Yes it could. Would it? Depends on the implementation and the optimisations that are made.