Std :: vector and copy constructors

Question

vector<X> v; X x; v.push_back(x); v.push_back(x); v.push_back(x); 

Why does this code invoke the copy constructor of class X 6 times ? (using g ++ 4.7.2 STL)

Please, I would like to know exactly what is happening under the hood with this particular STL.

Answer 1

When you insert x with push_back() , the memory is eventually redistributed to make room for the new element. Then, already inserted elements should be copied using the copy constructor X(const X&) .

If you insert

 v.reserve(3); 

redistribution is prevented at least during the first three push_back() , and as a result, there will only be three calls to X(const X&)

Answer 2

You can use the vector reserve to create space in the vector in front of the hand to speed up the addition of elements to the vector and also stop it.

Answer 3

Here's what happens:

Before the first push_back, the vector capacity (the number of elements that fit into the allocated space) is 0. Therefore, when you do the first push_back, it allocates space for 1 element and calls the copy constructor (1st call).

So, now the capacity is one, and you tell her to add another element. Thus, he should allocate more space, in this case, a place for another element and copy the original elements to a new space (2nd call). The second push_back again calls the copy constructor (third call).

Now you have capacity 2 and tell him to add another item. Therefore, he must allocate more space and copy elements to a new space (4th and 5th calls). Then the third push_back again calls the copy constructor (6th call).

As others have pointed out, you can use a reserve that will allocate space forward, avoiding the need for redistribution and, therefore, accessing the copy constructor.

Answer 4

The correct answer is that std::vector is implemented using a doubling array (see http://en.wikipedia.org/wiki/Dynamic_array ) and it calls about 2 * N times the copy constructor.

For example, for N = 100,000 it calls the copy constructor 231,071 times. As indicated, the number of redistributions can be reduced by calling v.reserve() .