CODEWITHSUNDEEP
c++performancedata-structures
Muhammad Rehan Qadri
Muhammad Rehan Qadri

Reputation: 7654

which is faster method to traverse an array

Compare following two codes:

for (int i = 0; i<array_size; i++)
  cout << array[i] << endl;

OR

int* p_end = array+array_size;
for (int* p_array = array; p_array != p_end; p_array++)
  cout << *p_array << endl;

Which one is faster?

Another question is if we just want to traverse then which is faster: link list or array? Thankyou!

Upvotes: 0

Views: 1314

Answers (3)

Glenn Teitelbaum
Glenn Teitelbaum

Reputation: 10333

Note the following:

for (int i = 0; i<array_size; i++)
  cout << array[i] << endl;

Each loop you must - compare i to array size, increment i, add i to array

int* p_end = array+array_size;
for (int* p_array = array; p_array != p_end; p_array++)
  cout << *p_array << endl;

Each loop you must - compare p_array to p_end, increment p_array (there is no add here)

So it would seem that the second loop - becuase it does not have to do an add should be faster

However - optimizers can do quite a lot so I would recommend compiling both and then comparing the asm for each loop

Also for your second question - Arrays are faster than linked lists to traverse because of the load time for each node and because they take more memory so fewer nodes can be cached

Upvotes: 0

Joe Z
Joe Z

Reputation: 17936

The first one is likely to be faster on an array.

The second one terminates on finding a zero entry in the structure. It really isn't the same thing. But suppose you changed your code to read:

p_array = array;
for (int i = 0; i < array_size; ++i, ++p_array)
    cout << *p_array << endl;

That loop would probably take the same amount of time as the first one with any modern compiler. (In all actuality, the cost of cout would swamp everything anyway.)

The best approach for iterating through a container is really dictated by the container. vector<T> allows O(1) random access via operator[]. Also, its iterators offer O(1) operator++. In contrast, a container like list<T> only lets you use operator++, and it's O(1).

And final thought: You likely want to stick to pre-increment instead of post-increment in C++ when you can.

Upvotes: 0

ScarletAmaranth
ScarletAmaranth

Reputation: 5101

array[i] is potentially faster because the compiler knows you're not aliasing your pointer to someplace you really shouldn't.

Lists are much slower to traverse because of indirection imposed inbetween every node - this will ruin your caches and cause many a cache miss, which is probably the worst thing that can happen to a modern processor.

Upvotes: 1

Related Questions