12

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?

Niall
  • 30,036
  • 10
  • 99
  • 142
Humam Helfawi
  • 19,566
  • 15
  • 85
  • 160
  • 1
    This may answer your question: http://stackoverflow.com/questions/2208293/what-is-the-most-efficient-way-to-append-one-stdvector-to-the-end-of-another – Nathan Cooper Feb 12 '16 at 09:40
  • It depends on whether the iterators are input iterators or strictly stronger. For anything stronger you can get the count with `distance`. It's QoI, but any decent implementation should not reallocate more than once for this. – Kerrek SB Feb 12 '16 at 09:46
  • Both `libstdc++` and `libc++` implementations reserve space for whole sequence at once if given at least forward iterators. – Revolver_Ocelot Feb 12 '16 at 09:49
  • On a side note: Although insert will call reserve internally, both variants may actually produce different assembly code and result in different performance. – MikeMB Feb 12 '16 at 10:52

3 Answers3

15

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.
dkg
  • 1,775
  • 14
  • 34
  • Thanks. There is something I could not get. The two cases are implementation dependable. So I should dig into my compiler implementation. Or they are cases that Should I predict them depending on my code – Humam Helfawi Feb 12 '16 at 11:02
  • You should predict the case. ie if you know you will give an input iterator better call `reserve` before. – dkg Feb 12 '16 at 13:21
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.

Niall
  • 30,036
  • 10
  • 99
  • 142
  • what do you mean it won't be guaranteed in your last paragraph? It will and there would be zero allocations – Alexey Andronov Feb 12 '16 at 09:50
  • @AlexeyAndronov. It could call reserve even it has just enough space, the algorithms are not specified, so in theory it could want to allocate a bit more as a buffer. – Niall Feb 12 '16 at 09:52
  • [link](http://www.cplusplus.com/reference/vector/vector/insert/): _"This causes an automatic reallocation of the allocated storage space if -and only if- the new vector size surpasses the current vector capacity."_ – Alexey Andronov Feb 12 '16 at 09:55
  • @AlexeyAndronov. The wording in the standard is weaker than that. But point taken, I've removed the note. – Niall Feb 12 '16 at 10:00
0

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.

skypjack
  • 49,335
  • 19
  • 95
  • 187
  • 1
    OP is asking something different: he wants to know if pre-reservation happens before insertion. – Sergey Kalinichenko Feb 12 '16 at 09:41
  • You mean if it reserves as a whole, being known the number of objects to be inserted? It's obvious indeed that the insert somehow takes cares of reallocations, thus you can look at it as *reserve-size-plus-one* request for each step (OK, apart for the performance, logically speaking). – skypjack Feb 12 '16 at 09:47
  • 2
    It appears to me that OP wants to know if multiple allocations could happen during `insert`, and also if the (implicitly) reserved size could significantly exceed the actual size. – Sergey Kalinichenko Feb 12 '16 at 09:52
  • Uhm... Got it, I guess it's implementation dependent, I'm looking at libstdc++ as an example to know how they goes with that. – skypjack Feb 12 '16 at 09:55
  • Wait, I agree with @Niall indeed, the number of element is not known, thus the vector can do its best to reduce the reallocations and nothing more... – skypjack Feb 12 '16 at 09:58