diradon's blog

array of vector is faster than vector of vector for storing adjaceny list?
By diradon, history, 4 years ago, In English

Hi all, I recently came across an issue that I am unable to comprehend. While solving problem 1337C, I used the same code twice except using a vector<vector<int> > adj(n) in 83595937 and vector<int> a[n] in 83693762. For some reason, the first submission timed out and the second one passed. I thought maybe it has something to do with the fact that vectors aren't preallocating the proper space but that shouldn't be the case as I am mentioning the size n while declaring the vector of vector as well. I searched for this problem on the internet but the discussion is almost always about vector vs arrays and not 2D containers. Thanks for the help!

EDIT: it's solved! Thanks to vipinkumar17 for pointing it out. Passing vvi as reference fixed the problem: 83860879

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

Comments Comments (4)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

vector<vector> adj when passed as an argument to dfs function makes copies of itself each time recursion is called.On the other hand vector adj[] does not make copies of itself when dfs is called recursively. I think this is the reason.Please Correct me if i am wrong.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Oh yes you're spot on! Sorry this is kinda embarrasing. Should have thought about it. Passing it as a reference fixed the problem: 83860879

    Thanks a lot!

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by diradon (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

diradon in this case you survived TLE with adding & to your vector but there are cases that just arrays work. At all using arrays decreases time limit. those cases are rare but exist!

→ Reply