Vectors are internally initialized as dynamic arrays with size "X", as elements are inserted
if current size becomes equal to "X" then it has to be doubled and earlier elements needs to be copied,
This can lead to slowing up the process.
So, if you know the size of size of array beforehand, better initalize with that size otherwise "push_back/emplace_back"
will trigger resizing/copying leading to slower execution.
vectors have 2 methods
vector<int> vec; // size = 0; capacity = 0;
vec.push_back(1) // size =1 , capacity = 1;
vec.push_back(2) // size =2 , capacity = 2;
vec.push_back(1) // size =3 , capacity = 4;
vec.push_back(1) // size =4 , capacity = 4;
vec.push_back(1) // size =5 , capacity = 8;
...
...Comparsion b/w timing if we need to push INT_MAX elements in vector.
I did a small experiment to compare the timing of pushing INT_MAX number of elements to a vector vs initializing a vector with size INT_MAX, and copying elements. Difference of run times is not marginal rather huge.
void f1() {
double startTime = (double) clock();
vector<int> result;
int size = INT_MAX;
for (int i = 0 ; i < size; i++) {
result.push_back(i);
}
double endTime = (double) clock();
cout <<"f1 -> push_back time taken " << (endTime - startTime) <<endl;
}void f3() {
double startTime = (double) clock();
vector<int> result(INT_MAX, -1);
for (int i = 0 ; i < result.size(); i++)
result[i] = i;
double endTime = (double) clock();
cout <<"f3-> static time taken " << (endTime - startTime) <<endl;
}When we just keep on pushing INT_MAX number of elements, It has to resize 32 times ( 0,1,2,4,8,16, 2^31) and copy contents on every resize.
f1 -> push_back time taken 32578
f1 -> push_back time taken 26017
f1 -> push_back time taken 26998f3-> static time taken 15340
f3-> static time taken 14339
f3-> static time taken 14168Time taken by static size initialization is almost half of case where we don't initialize the size and keep pushing.