Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Speed accessing a std::vector by iterator vs by operator[]/index?

Say, I have a

std::vector<SomeClass *> v; 

in my code and I need to access its elements very often in the program, looping them forward and backward .

Which is the fastest access type between those two ?

Iterator access:

std::vector<SomeClass *> v; std::vector<SomeClass *>::iterator i; std::vector<SomeClass *>::reverse_iterator j;  // i loops forward, j loops backward for( i = v.begin(), j = v.rbegin(); i != v.end() && j != v.rend(); i++, j++ ){     // some operations on v items } 

Subscript access (by index)

std::vector<SomeClass *> v; unsigned int i, j, size = v.size();  // i loops forward, j loops backward for( i = 0, j = size - 1; i < size && j >= 0; i++, j-- ){     // some operations on v items } 

And, does const_iterator offer a faster way to access vector elements in case I do not have to modify them?

like image 896
Simone Margaritelli Avatar asked Mar 26 '10 15:03

Simone Margaritelli


People also ask

Is linked list faster than vector?

For example, taking a bunch of random integers and inserting them in sorted order into a vector or a linked list -- the vector will always be faster, regardless of the number of items total, due to cache misses when searching for the insertion point in the linked list.

Is std::vector fast?

A std::vector can never be faster than an array, as it has (a pointer to the first element of) an array as one of its data members. But the difference in run-time speed is slim and absent in any non-trivial program. One reason for this myth to persist, are examples that compare raw arrays with mis-used std::vectors.

Are iterators faster than indexing?

Depending on the actual container, incrementing an iterator might be faster than indexing (think linked lists).

How do you compare iterator values?

To compare the values that two iterators are pointing at, dereference the iterators first, and then use a comparison operator. Operator= -- Assign the iterator to a new position (typically the start or end of the container's elements).


2 Answers

The performance difference is likely negligable or none (the compiler might optimise them to be identical); you should worry about other things, like whether your program is correct (a slow but correct program is better than a fast and incorrect program). There are other advantages to using iterators though, such as being able to change the underlying container to one with no operator[] without modifying your loops. See this question for more.

const_iterators will most likely have none, or negligable, performance difference compared to ordinary iterators. They are designed to improve the correctness of your program by preventing modifying things that shouldn't be modified, not for performance. The same goes for the const keyword in general.

In short, optimisation should not be a concern of yours until two things have happened: 1) you have noticed it runs too slowly and 2) you have profiled the bottlenecks. For 1), if it ran ten times slower than it could, but is only ever run once and takes 0.1ms, who cares? For 2), make sure it's definitely the bottleneck, otherwise optimising it will have nearly no measurable effect on performance!

like image 112
AshleysBrain Avatar answered Sep 28 '22 00:09

AshleysBrain


A simple loop-based benchmark has been fulfilled. I used VS 2010 SP1 (release configuration).

  1. Use iterators (*it = *it + 1;)
  2. Use indices (vs[i] = vs[i] + 1;)

In several billions of iterations the second approach turned out to be a bit faster, by 1%. The result (indices are slightly faster than iterators) is reproducible but the difference, as I said, is very small.

like image 20
borx Avatar answered Sep 28 '22 01:09

borx