ShivanshJ's blog

Are pairs much faster than vectors (C++)?
By ShivanshJ, history, 22 months ago, In English

So, I was doing this this problem and noticed the drastic difference between std::pair and std::vector in C++. I preferred to use std::vector over pairs as I don't have to write .first and .second every time.

Submission using std::vector (GETS TLE) View

Submission using std::pair (GETS AC easily) View

What could be the reason behind it?

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Woah, didn't know that, that's some crazy amount of time difference man. The vector solution is taking around 8000ms whereas pair one is running at around 250ms

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    similar bro , i also see a question i use vector of size 2 first it passed just 4 test case then i use pair it pass all 20 test case

    → Reply
»
22 months ago, # |
  Vote: I like it +10 Vote: I do not like it

If you know that your vectors are going to be of specific size, use std::array instead. So, the compiler knows beforehand how much memory to allocate. And, this can help improve run time. To be able to use std::array like vectors (syntactically) you could use typedef maybe, something like:

typedef array<int, 2> vect; // Name according to your likeness

void func(vect & a, vect & b) {
 // do your stuff
}
vect a = {2, 3};

// etc.
→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

$$${std::pair<T1, T2>}$$$ is faster than $$${std::vector<T>}$$$ with size $$$2$$$ the reason behind this is vectors are dynamic in nature (size can be modified) where as pairs are static such as array. You may read here as well!

PS: You may use $$${std::array<T, size>}$$$ or $$${std::tuple<T1, T2...>}$$$ as well.

→ Reply
»
16 months ago, # |
  Vote: I like it -51 Vote: I do not like it

amortised analysis

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes, I also faced a similar problem,

Question: https://www.geeksforgeeks.org/problems/minimum-edges/1?utm_source=geeksforgeeks&utm_medium=ml_article_practice_tab&utm_campaign=article_practice_tab

When i used vector<vector> adj[n+1], I got TLE where as vector<pair<int,int>> adj[n + 1] works fine.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    See my comment below, I think this is exactly the issue. Ask me if I need to clarify.

    → Reply
»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

At first I thought this was due to the better indexing of your dp array (thanks to cache optimisations).

But it turns out that my modified versions are still getting TLE. Fortunately, I think I understand what is going on. It is indeed because of cache optimisations. When you have a vector of pairs, the access to the pairs is very fast because they are contiguous in memory : it's easy to keep them in high speed caches. Whereas, if they are far apart, they will lie in different memory pages, so it is going to require much more time to access.

→ Reply