Why does the sequential vector :: push_back lead to a different number of constructor calls?

Question

class base { private: int k; public: base(const base& b){ this->k = bk; cout<<" c-ctor "<<endl; } base(int a = 10){ k = a; } ~base(){cout << "destructor called\n";} }; int main() { base b, b1(2); vector<base> m; cout << "first pushback" <<endl; m.push_back(b); cout << "2nd pushback" <<endl; m.push_back(b1); cout << "3rd pushback" <<endl; m.push_back(b1); cout << "4th pushback" <<endl; m.push_back(b); cout << "5th pushback" <<endl; m.push_back(b); cout<<" =============================================== "<<endl; return 0; } 

Outputs:

 first pushback c-ctor 2nd pushback c-ctor c-ctor destructor called 3rd pushback c-ctor c-ctor c-ctor destructor called destructor called 4th pushback c-ctor 5th pushback c-ctor c-ctor c-ctor c-ctor c-ctor destructor called destructor called destructor called destructor called =============================================== destructor called destructor called destructor called destructor called destructor called destructor called destructor called 

Why do ^th push_back result in i number of copy constructor calls?

Isn't this a resizing effect (i.e., copying the original vector again) and a rather inefficient way to insert elements into the vector?

Why does 4 ^th push_back have a different behavior than 2 ^th , 3 ^th abd 5 ^th push_back ?

Demo

Answer 1

Never mind. vectors are redistributed each time its size reaches its capacity . All elements are copied from the old vector to the new vector.

Typically, twice the original capacity is allocated for a new vector.

• Up to 1st push_back capacity is 1. Therefore, it does not need to be reallocated.
• For the 2nd push_back capacity should double, so two calls to the copy constructor are created, first copy the old element to the new vector and the second for push_back . Capacity is now 2.
• The third push_back should redistribute the vector again, since the capacity is now 2. After the redistribution capacity becomes 4.
• Now redistribution does not occur, therefore one call to copy ctor (for push_back ). Capacity 4 more.
• Redistribution occurs for the 5th push_back , and 4 old elements and one new element ( push_back ) are copied to the new vector. Capacity is now 8.

If you go further, you will see that the redistribution will occur on the 9th push_back .

In addition, destructors must be called during redistribution, when the older vector is no longer needed and, therefore, the members in it must be destroyed.

Answer 2

std::vector can be thought of as a dynamic array. As such, it grows when necessary, and this requires that the vector allocate more memory and copy the existing elements of the vector to a new large memory.

Existing objects in the old memory are then destroyed.

If you know in advance how many elements you need in the vector, you can reserve memory for the vector. In this case, the vector does not need to redistribute and copy the data until you press a new capacity.

I really recommend that you learn more about std::vector , especially about the difference in its capacity and size.

Answer 3

The vector must expand to accommodate the new element. This requires copying existing elements to a new buffer.

If your class was noexcept moved constructively, it instead created calls to the move constructor.

The reason for not every push_back leads to memory redistribution in the vector, probably due to the standard implementation of the library, which tries to reserve additional memory after resizing to avoid too frequent use. This is done in the freedom of implementing vector to do this, and there are several strategies for determining the amount of redundancy.

Answer 4

To take a step backward, there is a key requirement std :: vector : elements in a vector must be stored contiguously. This means that you can safely use the pointer to an element in the vector as a raw pointer to this type of element and therefore you can use the semantics and arithmetic of the pointer, as you would expect, with an array of fixed size.

This also means that accessing any element of the array by its index is very fast and takes the same time regardless of the size of the array and the index of the specific element you are accessing (this is called O (1) or "constant time").

The penalty that must be paid for this allowance is redistribution. When a vector is created, you usually don’t know how many elements you will use, so you allocate some amount of contiguous memory to store a certain amount of elements. If you continue to add to the vector, you will exceed this initial distribution. But you cannot just increase the amount of memory used by your vector, because your program may have allocated memory immediately after your current vector to some other variable. The only way to ensure that vector elements remain contiguous is to select a new block large enough to contain all elements, including the extra one, and then copy all elements to this new location.

As others noted, it is enough to distribute the size of the array exponentially, highlighting 1.5 or 2 times the original size of the array for each excess capacity. This reduces the regularity of the redistribution of the entire array as it grows.

If instead you want to get a collection of elements where it is always fast enough to add an element (or at least always takes as long), you can use a linked list ( std :: list ), but then you can no longer quickly access to any element by index ("random access").

Answer 5

"a pretty inefficient way to insert elements into a vector"

As others have pointed out, you can request std::vector reserve enough memory for you in the first instance to allow elements to click on your vector to this limit with the need for redistribution. If you change the code to add the following call to reserve :

 vector<base> m; m.reserve(5); cout << "first pushback" <<endl; 

Using reserve will not change the size of your vector, but enough memory will be allocated to allocate an adjacent vector of this size to avoid redistribution. In your example, you will see a significant reduction in the number of constructors and destructors created. If you know (roughly evenly) the size of your vector and the construction / destruction of the type of road, this can go a long way for your code.

Note that reserve very different from resize - the first is most useful when you click elements on a vector (your example), the second creates a fully filled vector of elements, starting the copy constructor N times; this is useful when subsequently accessing and changing items through the index operator.