baibhav_21's blog

Are vectors slower than arrays?
By baibhav_21, history, 2 years ago, In English

I was trying out a trie problem, and I was stuck on it for a long time, I had defined the trie using a vector and every time was submitting my answer with some minor changes it showed me memory limit exceeded, or sometimes it was even giving me a TLE, After a while, I changed my vector used in the definition of the trie to the array, and in the first go itself My submission got accepted and not only that with vectors I was having a runtime of around 1762 ms and Memory of around 524300 KB and with arrays they both got optimized to 1341 ms and 366400 KB.

Can anybody pls confirm me if arrays are faster than vectors or is there is something I am missing out?

The submission that is giving me the error (using vectors)- 180171998 The submission that is giving me an ac (using arrays)- 180172097

  • Vote: I like it
  • -18
  • Vote: I do not like it

»
2 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Well, I would assume that the struct with array has a flat structure which is stored as continuous block of memory, while for the vector case what is stored continuous is vector object itself (and its fields, sizeof(vector), basically) and your array inside vector is actually stored as a pointer to a memory on a heap. Accessing it is slower due to one more jump in memory and it not being in cache memory. With the array case you may assume that as long as you have some node, you can access the array very fast (it's in the cache), while for vector it may not be the case.

Btw, you could have defined a global pool like and there would not have been raw news in your code.

Node pool[SOME_BIG_NUMBER];
Node* getNode() { static int usedCnt = 0; return &pool[usedCnt++]; }

So you see the problem, it's not precisely about arrays and vectors. It's about the reasons why it is so. Bonus: guess what happens if that array of yours is a dynamic array, not the static one.

→ Reply