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

Question

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.

Have you tried adding `v.reserve(n)` after declaring `v` in the first example? That would avoid reallocation overhead, making the `vector` roughly equivalent to the raw array (even more equivalent if you can switch to `emplace_back`. All that said, unclear why you wouldn't just fill the thing in directly by initializing with `n` copies of a single pair, given the values are all the same. — ShadowRanger, Jun 27 '20 at 19:55
In the second example the size of the array of pairs is known at compile time, and will moreover be placed on the stack, as compared to the first example where you are using a dynamic container, which is (ignoring any small vector optimiztions) allocated and re-allocated on the heap. You could always try out the first example but invoking reserve to pre-reserve an appropriate size in the dynamically allocated vector, to at least avoid re-allocation. — dfrib, Jun 27 '20 at 20:07
The answers here are correct, but it's hard to imagine that any vector inefficiencies would cause a TLE when an array of the same size fits on the stack. It's just too small to be a real issue. There is probably a more serious problem somewhere else in your code. Maybe a buffer overrun that has a different effect when you move the array. — Matt Timmermans, Jun 27 '20 at 20:52

JeJo · Accepted Answer · 2020-06-27T20:25:41.833

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;

score 0 · Answer 2 · answered Jun 27 '20 at 20:07

0

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.

answered Jun 27 '20 at 20:07

Amir Kadyrov

1,253
4
9

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

2 Answers2