Combining two std :: vector - which method is more efficient and how / why?

Consider the following scenario:

std::vector<int> A;
std::vector<int> B;
std::vector<int> AB;

      

I want to AB

have content A

and then content B

in the same order.

Approach 1:

AB.reserve( A.size() + B.size() ); // preallocate memory
AB.insert( AB.end(), A.begin(), A.end() );
AB.insert( AB.end(), B.begin(), B.end() );

      

Approach 2:

std::vector<int> AB ( A.begin(), A.end() ); // calling constructor
AB.insert ( AB.end(), B.begin(), B.end() );

      

Which of the above methods is more effective? What for? Is there any other way that is more efficient?

+3


source to share


3 answers


I think the former will always be faster than the latter because it will only do one memory allocation and the latter will probably have to be reallocated at least once. But my measurements seem to indicate that for sizes under 100,000 this is even faster:

std::vector<int> AB(A.size() + B.size());
std::copy(A.begin(), A.end(), AB.begin());
std::copy(B.begin(), B.end(), AB.begin() + B.size());

      



My guess is that this is not only due to the fact that it only does one allocation and does not reallocate, but it doesn't even need to check if it should reallocate. The downside is that it can zero out all memory first, but I think CPUs are good at this.

+1


source


The first one is probably more efficient as you can guarantee that only one memory allocation will be performed. In the second case, there is a chance (most implementations) that the allocation for A.size()

will be done during vector construction, and then insert

will trigger the second distribution, since it should grow by B.size()

. p>



+8


source


Approach 1 does not redistribute, whereas Approach 2 can redistribute multiple times and in practice is likely to redistribute once. So approach 1 is better.

+3


source







All Articles