Geek Answers Handbook

Does std :: vector :: insert a fallback by definition?

When calling the insert member function on std::vector will it reserve before "canceling" new elements? I mean, standard warranty or not?

In other words, should I do this as follows:

 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?

+7
source share
3 answers

Regarding the complexity of the function [link] :

Linear in the number of inserted elements (copy / move) plus the number of elements after the position (move).

In addition, if the InputIterator in the range insert (3) is not at least the category of the direct iterator (i.e., only the input iterator), the new capacity cannot be determined in advance, and the insert is an additional logarithmic complexity in size (redistribution).

Therefore, there are two cases:

  • New capacity can be determined, so you won’t need to reserve
  • The new capacity cannot be determined, so the reserve call should be useful.
+13
source

std::vector::insert is std::vector::insert by definition?

Well no; depends on current power.

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

Causes redistribution if the new size is larger than the old capacity .

If the allocated memory capacity in vector is large enough to accommodate new elements, additional allocations for vector not required. So no, then he will not reserve the memory.

If the vector capacity is not large enough, a new block is allocated, the current content is moved / copied, and new elements are inserted. The exact distribution algorithm is not specified, but, as a rule, it will be the same as in the reserve() method.

... or another better approach?

If you are worried about too many selections when inserting elements into vector , then calling the reserve method with the size of the expected number of elements to add will minimize the selection.

vector reserve before / any insertions? Those. Is enough power allocated in a single allocation?

There is no guarantee. How to know the distance between input iterators? Given that the insert method can take an InputIterator (i.e. a one-pass iterator), it cannot calculate the expected size. Can a method calculate the size if iterators are somewhere else (e.g. pointers or RandomAccessIterator )? Yes it can. Will it be? Depends on the implementation and optimizations that are made.

+2
source

From the documentation it seems that:

Causes redistribution if the new size () is larger than the old capacity ().

Remember also that in this case all iterators and links are invalid.

It goes without saying that the redistribution is responsible for insert , and if you look at these operations one at a time, then at each step, a sequential operation of the backup size plus one is performed. <w> You can argue that calling reserve at the top of the insert will speed everything up when more than one redistribution occurs ... Well, this can help, but it mostly depends on your real problem.

+1
source

More articles:


All Articles