Iterator or for loop?

[Andrea Crotti]

The "standard" way to iterate over a container should be:

std::vector<int>::iterator iter;
for (iter=var.begin(); iter!=var.end(); ++iter) {
...
}

for example, right?
But I always end up using
for (size_t i=0; i < var.size(); ++i) {
...
}

(unless I'm using maps)

because it's much shorter to write and I don't need the iterator. But
are there any real differences using this two different possibilities?

 

[Joshua Maurice]

The "standard" way to iterate over a container should be:

std::vector<int>::iterator iter;
for (iter=var.begin(); iter!=var.end(); ++iter) {
    ...    

}

for example, right?
But I always end up using
for (size_t i=0; i < var.size(); ++i) {
    ...

}

(unless I'm using maps)

because it's much shorter to write and I don't need the iterator.  But
are there any real differences using this two different possibilities?

Some compilers might optimize one better than the other. For
std::vector, I hope that both for loops would produce the same
assembly output, but I am frequently surprised as the bad quality of
some commercial compilers.

Also, some containers don't support constant time indexing, so
iterators is your only real option, such as std::map.

Also, C++0x will solve this typing annoying nicely with auto, and even
better with foreach loops aka range based for loops.

 

[Chris Gordon-Smith]

I read (I think in in one of Herb Sutter's books) that this entails
calculating var.end() every time round the loop, and that using
a local variable set to var.end() can be more efficient. I wondered
whether compilers would be smart enough to optimise this without
any special user coding.

Some compilers might optimize one better than the other. For
std::vector, I hope that both for loops would produce the same
assembly output, but I am frequently surprised as the bad quality of
some commercial compilers.

Also, some containers don't support constant time indexing, so
iterators is your only real option, such as std::map.

Also, C++0x will solve this typing annoying nicely with auto, and even
better with foreach loops aka range based for loops.

Some compilers might optimize one better than the other. For std::vector, I hope that both for loops would produce the same
assembly output, but I am frequently surprised as the bad quality of some commercial compilers.

Also, some containers don't support constant time indexing, so iterators is your only real option, such as std::map.

Also, C++0x will solve this typing annoying nicely with auto, and even better with foreach loops aka range based for loops.

It will be great if it allows a foreach that doesn't require the use
of a function or function object outside the loop. While I
think this technique may be useful in some cases, I think it can
be cumbersome. I recently used a foreach for what would otherwise
been a fairly straightforward loop, but found myself creating a function
object and then ensuring that it was constructed with the
right context, which would have otherwise been available in the body
of the loop 'for free'.

Chris Gordon-Smith
www.simsoup.info

 

[Ian Collins]

I read (I think in in one of Herb Sutter's books) that this entails
calculating var.end() every time round the loop, and that using
a local variable set to var.end() can be more efficient. I wondered
whether compilers would be smart enough to optimise this without
any special user coding.

For std::vector, end() almost certainly optimises a way to a constant
(end doesn't have to be calculated in the loop).

It will be great if it allows a foreach that doesn't require the use
of a function or function object outside the loop. While I
think this technique may be useful in some cases, I think it can
be cumbersome. I recently used a foreach for what would otherwise
been a fairly straightforward loop, but found myself creating a function
object and then ensuring that it was constructed with the
right context, which would have otherwise been available in the body
of the loop 'for free'.

One bit advantage of function or function objects is that they can be
testing in isolation.

 

[Chris Gordon-Smith]

Erm - sorry for the messed up formatting in my post of a few
minutes ago.

 

[Juha Nieminen]

For std::vector, end() almost certainly optimises a way to a constant
(end doesn't have to be calculated in the loop).

Only if the compiler can prove that the vector doesn't change in the
body of the loop. That may be difficult to prove especially in cases
where the vector is being given as parameter to some function.

 

[Ian Collins]

Only if the compiler can prove that the vector doesn't change in the
body of the loop. That may be difficult to prove especially in cases
where the vector is being given as parameter to some function.

Did I really say constant? I should have said the call will be
optimised away. The value of end is adjusted when an insetion or
deletion occurs, rather then when end() is called.

 

[Fred Zwarts]

I read (I think in in one of Herb Sutter's books) that this entails
calculating var.end() every time round the loop, and that using
a local variable set to var.end() can be more efficient. I wondered
whether compilers would be smart enough to optimise this without
any special user coding.

Similarly, this entails calculating var.size() every time round the loop.
Why should var.end() be more difficult to calculate than var.size()?
One may expect similar compiler optimizations,
or else use similar tricks using a local (const) variable.

 

[Andrea Crotti]

Similarly, this entails calculating var.size() every time round the loop.
Why should var.end() be more difficult to calculate than var.size()?
One may expect similar compiler optimizations,
or else use similar tricks using a local (const) variable.

Yes I also thought that.
Actually I thought that the "normal" for loop could have been slower for
that, and well if the container is not forced to be immutable during the
loop it should be computed every time.

From my understanding only if the container is passed as a reference to
const it should be easy (or possible) for the compiler to avoid
computing size()/end() all the time.

Correct?

 

[Fred Zwarts]

Yes I also thought that.
Actually I thought that the "normal" for loop could have been slower
for that, and well if the container is not forced to be immutable
during the loop it should be computed every time.

From my understanding only if the container is passed as a reference
to const it should be easy (or possible) for the compiler to avoid
computing size()/end() all the time.

Correct?

Passed to what?

If non-const references exists and can be accessed by functions called in the loop body,
these functions could still modify the container.

 

[Andrea Crotti]

Passed to what?

If non-const references exists and can be accessed by functions called in the loop body,
these functions could still modify the container.

Yes sure I wasn't clear, I just meant this

void func(const std::vector<int>& vec)
{
for (...)
vec...
}

if we pass a reference to const and we only use it what I said was correct?

 

[James Kanze]

On 12/22/10 01:46 PM, Chris Gordon-Smith wrote:

For std::vector, end() almost certainly optimises a way to a constant
(end doesn't have to be calculated in the loop).

For std::vector, end() certainly isn't a constant. It will
change anytime you grow the vector.

A really good compiler certainly could determine that it was
a loop invariant (if you are actually growing the vector in the
loop, you're likely to have problems with iter as well), but the
analysis isn't trivial, and in the cases I've actually measured,
it does make a (very small) difference.

With regards to the initial question, int the implementations of
std::vector that I've actually looked at, size is implemented:
size_t size() const { return end() - begin(); }
So using indexes and size() won't help anything.

I'd use whatever is most reasonable, until the profiler said
otherwise. For an experienced C++ programmer, that sounds like
the iterator version to me.

 

[James Kanze]

Yes sure I wasn't clear, I just meant this

void func(const std::vector<int>& vec)
{
for (...)
vec...
}

if we pass a reference to const and we only use it what I said
was correct?

The const is irrelevant, and makes no difference. If the
compiler can see all possible accesses through the reference,
and it can prove that no aliasing allows other accesses, it can
optimize. Otherwise, no.

Note that most optimizers date back to the days of C, and will
treat the reference (here) as a pointer. And the analysis isn't
trivial. But if this is a leaf function (calls no other
function, at least not in the loop), and there are no other
references or pointers used by the function (at least not in the
loop), it should be possible. (Note that member functions of
vector may inhibit the optimization, if they are not inlined, or
if the optimizer doesn't consider them as if they were inlined.)

 

[Bo Persson]

Passed to what?

If non-const references exists and can be accessed by functions
called in the loop body,
these functions could still modify the container.

And if we call lots of hard-to-analyze functions in the loop body, the
possible optimization of caching a call to v.end() will be miniscule.
We shouldn't do things more complicated than we have to.


Bo Persson

 

[Ian Collins]

For std::vector, end() certainly isn't a constant. It will
change anytime you grow the vector.

I know, that's why I corrected myself in a follow up post.

 

[James Kanze]

Fred Zwarts wrote:

[...]

And if we call lots of hard-to-analyze functions in the loop body, the
possible optimization of caching a call to v.end() will be miniscule.
We shouldn't do things more complicated than we have to.

And if we call lots of hard-to-analyze functions in the loop
body, the difference between hoisting the call to v.end() out of
the loop, and not hoisting it, won't be significant.

 

[Jorgen Grahn]

The "standard" way to iterate over a container should be:

std::vector<int>::iterator iter;
for (iter=var.begin(); iter!=var.end(); ++iter) {
...
}

for example, right?

It's more common to declare 'iter' inside for(...) if it's useless
after the loop.

But I always end up using
for (size_t i=0; i < var.size(); ++i) {
...
}

(unless I'm using maps)

because it's much shorter to write and I don't need the iterator.

It's the other way around for me -- even in C I use

void foo(const char* v, int len)
{
const char* end = v+len;
const char* p;
for(p = v; p!=end; ++p) bar(*p);
}

Sure it's more to type, but once I got the idea behind iterators I
liked it, and started being annoyed by that index. YMMV.

/Jorgen