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?
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 :
reserve should be useful.Does
std::vector::insertreserve by definition?
Yes, no; 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
vectorcallreservebefore 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.
From the documentation, it seems that:
Causes reallocation if the new size() is greater than the old capacity().
Be aware also that in such a case all the iterators and references are invalidated.
It goes without saying thus that reallocations are in charge of the insert and, if you look at those operations one at the time, it's as a consistent reserve-size-plus-one operation is made at each step.
You can argue that a reserve call at the top of the insertion would speed up everything in those cases when more than one reallocation takes place... Well, right, it could help, but it mostly depends on your actual problem.
