CODEWITHSUNDEEP
c++algorithmtime-complexitystdvectorstd-pair
user13825994
user13825994

Reputation: 13

Is it more efficient to use array of pairs than using vector pair?

I was getting TLE when I was using a vector of pair as:

vector<pair<int,int>> v;

for(int i=0;i<n;++i)
v.push_back(make_pair(a,b));

sort(v.begin(),v.end());

and it got accepted when I changed the code to:

pair<int,int> v[n];
for(int i=0;i<n;++i)
{
       v[i].first=a;
       v[i].second=b;
}
sort(v,v+n);

I want to understand the logic behind this.

Upvotes: 1

Views: 984

Answers (2)

JeJo
JeJo

Reputation: 32797

In these lines

vector<pair<int,int>> v;

for(int i=0;i<n;++i)
   v.push_back(make_pair(a,b))

you create a vector of std::pair<int,int>, and trying to put the element at the end of it while iterating n times. During these iterations, the v (vector of pairs), may undergo several reallocations as the std::vector::capacity will not be enough for inserting n elements. This is an expensive process as the whole vector needs to be deep copied to a new location which suits the new capacity. Hence your program gets slower for a larger n, as it needs to be reallocated for many times.

The solution is to use std::vector::researve to reserve the memory which we needed beforehand, (i.e. before the iteration and insertion start) so that, the expensive deep copy/ reallocations can be avoided. Meaning doing the following with the std::vector solution will also succeed the time limit issue.

#include <vector>
#include <utility>  // std::pair

std::vector<std::pair<int, int>> v;

const int n = 5; // lets say n = 5

v.reserve(n);   // now, reserve the memory for `n` pairs

for (int i = 0; i < n; ++i)
   // you can use `std::vector::emplace_back` to insert the pairs in place like this!
   v.emplace_back(a, b);

As a side note, please do not practice with using namespace std;

Upvotes: 2

Amir Kadyrov
Amir Kadyrov

Reputation: 1288

If you know count of pairs at compile time and this count is constant, use std::array. Otherwise you may use std::vector or another STL container.

Upvotes: 0

Related Questions