vector performance: iterator versus subscripting

[Matt Garman]

Is there any difference, performance-wise, accessing elements of a
vector using iterators or the subscript operator?

In other words, say I have a vector of strings:

vector<string> strvec;

After some processing, the vector has a very large (>50,000) number of
elements. Is there any performance difference in the following methods
of vector access?

vector<string>::iterator ii;
for (ii=strvec.begin(); ii!=strvec.end(); ++ii) {
// do stuff with *ii
}

Alternative:

unsigned long i;
for (i=0; i<strvec.size(); i++) {
// do stuff with strvec
}

I did make a quick and dirty test of this: I read in about 5 MB worth of
strings (the strings were random numbers generated in another program by
rand()) into a vector. I then output those strings to files, once using
iterators and once using vector subscripting. There was no difference
in runtime.

That test obviously isn't at all complete, but I was hoping some
knowledgeable folks had the answer(s)

Thanks,
Matt
email at: http://raw-sewage.net/index.php?file=email

 

[Ivan Vecerina]

| Is there any difference, performance-wise, accessing elements of a
| vector using iterators or the subscript operator?
Not a predictable difference, and most likely a negligible one.
....
| After some processing, the vector has a very large (>50,000) number of
| elements. Is there any performance difference in the following methods
| of vector access?
|
| vector<string>::iterator ii;
| for (ii=strvec.begin(); ii!=strvec.end(); ++ii) {
| // do stuff with *ii
| }
....
| unsigned long i;
| for (i=0; i<strvec.size(); i++) {
| // do stuff with strvec
| }
Other factors are likely to affect performance much more than
using indexing vs. iterators on std::vector.
For example, loading the value of strvec.end() or strvec.size() into
a local variable instead of calling the function at every iteration is
likely to make a more important (albeit small) performance difference.

Ideally, if all functions of std::vector are inlined, a compiler could
generate optimal code for both loop implementations.

An advantage of iterators is that it that they can be more flexible
if you later need to work with a different container type,
standard algorithms, or a subrange of the container.

So I would personally write the loop as:
typedef vector<string>::iterator It;
It end = strvec.end();
for( It scan = strvec.begin() ; scan != end ; ++scan )
{
string const& str = *scan;
... do stuff with str ...
}

Or, better, use a function object and the std::for_each() algorithm...

| I did make a quick and dirty test of this: I read in about 5 MB worth of
| strings (the strings were random numbers generated in another program by
| rand()) into a vector. I then output those strings to files, once using
| iterators and once using vector subscripting. There was no difference
| in runtime.
The file I/O and memory allocations would in any case have outweighed
the performance difference between the two loop implementations.


I hope this helped,
Ivan

 

[Harald Grossauer]

For example, loading the value of strvec.end() or strvec.size() into

a local variable instead of calling the function at every iteration is
likely to make a more important (albeit small) performance difference.

It is possible that the size or the last element of the vector changes
during the loop. Wouldn't that be a problem if .end() resp. .size() are
saved to local variables before?

 

[Peter Koch Larsen]

It is possible that the size or the last element of the vector changes
during the loop. Wouldn't that be a problem if .end() resp. .size() are
saved to local variables before?

Yes. In this case, you can not store the end() before the loop starts.
But do not be that obsessed with performance. Write the code, and if it runs
to slowly profile it and eliminate bottlenecks.

Kind regards
Peter

 

[Ivan Vecerina]

| "Harald Grossauer" <[email protected]> skrev i en meddelelse
| | > > For example, loading the value of strvec.end() or strvec.size() into
| > > a local variable instead of calling the function at every iteration is
| > > likely to make a more important (albeit small) performance difference.
| >
| > It is possible that the size or the last element of the vector changes
| > during the loop. Wouldn't that be a problem if .end() resp. .size() are
| > saved to local variables before?
| >
|
| Yes. In this case, you can not store the end() before the loop starts.
| But do not be that obsessed with performance. Write the code, and if it
runs
| to slowly profile it and eliminate bottlenecks.

Ah, the fine line between "premature optimization"
and "avoiding unnecessary pessimization" ;-)

In this case, I would consider it a matter of style (I have a
macro in my editor to automatically generate a for-each like loop
with a stored end bound).

But of course, as I had mentioned in my first reply, using for_each()
is a first choice if a functor can be provided easily.

Regards,
Ivan