Is it faster to use push_back(x) or using an index (capacity)?

June 1, 2023

I learned 2 ways of inserting elements into a vector.

And I’ve been wondering which way is faster since I’m working with time limits.

Method 1:

int n;
cin>>n;
vector<int> v(n);
for(int i = 0;i<n;i++){
  cin>>v[i];
}

Method 2:

int n;
cin>>n;
vector<int> v;
for(int i = 0;i<n;i++){
  int x;
  cin>>x;
  v.push_back(x);
}

If you have a better method to suggest, it’d be appreciated!

>Solution :

Both have issues:
You should be using reserve(n)

int n;
cin >>  n;
vector<int> v;
v.reserve(n);
for(int i = 0; i < n; ++i){
    int x;
    cin >> x;
    v.emplace_back(x);
}

In the first version: Setting size.

Here you have the issue that you are constructing all the elements in the array. Now for integers this may be insignificant. But if we extend this to non integer types that have a constructor that needs to be called for each element and then you are using the assignment operator to copy over them.

The second option: push_back

Here you run into the risk of the underlying storage being reallocated (potentially multiple times). Each time you re-allocate you need to copy the data from the old storage to the new storage.

Again this hurts for integers but really hurts for types with constructors and destructors.

Prefer: emplace_back()

Rather than pushing where you need a fully constructed object. You can use emplace_back and pass in the objects used to construct the object. This allows the vector to construct the object in place. If you have simple integers or classes with effecient move semantics then not an issue but worth it as a general habit.