CODEWITHSUNDEEP
c++arraysalgorithmgraphstl
Bibek Bhattarai
Bibek Bhattarai

Reputation: 89

Why is array considered better than STL containers?

array vs. std::queue, which is better in terms of time and why?

I have written one graph processing algorithm in which frontier vertices are stored in std::queue and are accessed using push_back() and pop_front(). When I re-implemented the frontier with array with front and end pointers pointing to the start and end of the frontier vertices, I get the better result in terms of time. Is array really faster than queue for large enough size of data?

Upvotes: 0

Views: 139

Answers (1)

Gregg
Gregg

Reputation: 2604

The array is faster for most machines, because the contiguous elements of an array can be loaded in the same cache line (or pre loaded to the cache on a pre-need basis). Since a L1 cache read is 200 times faster than a main memory access, anything that requires a pointer fetch, will likely not be in cache and takes the much longer main memory fetch cycle.

https://www.youtube.com/watch?v=YQs6IC-vgmo

Upvotes: 1

Related Questions