std::vector iterator or index access speed question

Question

Just a stupid question .

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?

Thank you in advantage.

Answer 1

I believe that vector iterators are implemented as pointers internally (in a good STL implementation), so in general there should be negligible performance difference between the two idioms. But if you want to know how these perform on your platform, why don't you measure it with a little test program? I don't think it would take more than 5 minutes to measure execution time of e.g. 1 million iterations with both variants...

Answer 2

In terms of speed, I think might be almost same. Better, you can profile and check anyway.

At least you can reduce the number of variables used :)

for( i = 0; i < size ; i++){
    // some operations on v items
    v[i];
    v[size-i+1];
}

About const_iterator: Pls refer my Q: Are const_iterators faster ?

Answer 3

As always, it depends. Normally I wouldn't think you'd see any kind of difference, but only you can determine that by profiling your code. Some compilers implement vector iterators as raw pointers, and some don't. Also, in debug builds, some compilers may be using a checked iterator, which may be slower. But in production mode it may not be any different. Profile it and see.

Answer 4

If speed matters, then you should have time and will to run a profiler on it and see which works best in your case.

If it doesn't matter, then you are performing premature optimization and should STOP doing it.

Answer 5

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!

Answer 6

You are not only prematurely optimizing, you are micro-optimizing. This is an evil almost as bad as the former (the difference being that very, very, very rarely it is actually necessary to micro-optimize). Put the two together and you've got a recipe for disaster.

If you run a profiler and find this area of code is a bottleneck then you will need to optimize. You don't optimize by trying to reduce your loop from taking 23 clock cycles to 22. You optimize by finding ways to reduce the O() of your algorithm. But until you run a profiler you should be paying more attention to design than any other concern.

Answer 7

I'd go for iterators, but what I would optimize is calling end() in the loop and would change preincrement to postincrement. I.e. I'd

std::vector<SomeClass *> v;
std::vector<SomeClass *>::iterator i,ie;
std::vector<SomeClass *>::reverse_iterator j,je;

// i loops forward, j loops backward
for( i=v.begin(),ie=v.end(), j=v.rbegin(),je=v.rend(); i!=ie && j!=je; ++i,++j ){
    // some operations on v items
}

And I don't think it's premature microoptimization, it's just writing better code. Much less evil than calling every attempt to write efficient code premature microoptimization and substituting thinking with profiling.