Iterator or for loop?

Discussion in 'C++' started by Andrea Crotti, Dec 21, 2010.

  1. 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?
    Andrea Crotti, Dec 21, 2010
    #1
    1. Advertising

  2. On Dec 21, 3:09 pm, Andrea Crotti <> wrote:
    > 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.
    Joshua Maurice, Dec 21, 2010
    #2
    1. Advertising

  3. On Tue, 21 Dec 2010 15:12:49 -0800 (PST), Joshua Maurice <> wrote:
    > On Dec 21, 3:09 pm, Andrea Crotti <> wrote:
    >> The "standard" way to iterate over a container should be:
    >>
    >> std::vector<int>::iterator iter;
    >> for (iter=var.begin(); iter!=var.end(); ++iter) {
    >>     ...    
    >>
    >> }

    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 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.
    >>     ...
    >>
    >> }
    >>
    >> 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.


    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
    Chris Gordon-Smith, Dec 22, 2010
    #3
  4. Andrea Crotti

    Ian Collins Guest

    On 12/22/10 01:46 PM, Chris Gordon-Smith wrote:
    > On Tue, 21 Dec 2010 15:12:49 -0800 (PST), Joshua Maurice<> wrote:
    >> On Dec 21, 3:09 pm, Andrea Crotti<> wrote:
    >>> The "standard" way to iterate over a container should be:
    >>>
    >>> std::vector<int>::iterator iter;
    >>> for (iter=var.begin(); iter!=var.end(); ++iter) {
    >>> ...
    >>>
    >>> }

    > 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).

    >> 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'.


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

    --
    Ian Collins
    Ian Collins, Dec 22, 2010
    #4
  5. On 22 Dec 2010 00:46:48 GMT, Chris Gordon-Smith <> wrote:

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

    > On Tue, 21 Dec 2010 15:12:49 -0800 (PST),

    Joshua Maurice <> wrote:
    >> On Dec 21, 3:09 pm, Andrea Crotti <> wrote:
    >>> The "standard" way to iterate over a container should be:
    >>>
    >>> std::vector<int>::iterator iter;
    >>> for (iter=var.begin(); iter!=var.end(); ++iter) {
    >>>     ...    
    >>>
    >>> }

    > 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 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.

    > 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
    >
    >
    Chris Gordon-Smith, Dec 22, 2010
    #5
  6. Ian Collins <> wrote:
    >> 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).


    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.
    Juha Nieminen, Dec 22, 2010
    #6
  7. Andrea Crotti

    Ian Collins Guest

    On 12/22/10 07:36 PM, Juha Nieminen wrote:
    > Ian Collins<> wrote:
    >>> 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).

    >
    > 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.

    --
    Ian Collins
    Ian Collins, Dec 22, 2010
    #7
  8. Andrea Crotti

    Fred Zwarts Guest

    "Chris Gordon-Smith" <> wrote in message
    news:
    > On Tue, 21 Dec 2010 15:12:49 -0800 (PST), Joshua Maurice
    > <> wrote:
    >> On Dec 21, 3:09 pm, Andrea Crotti <> wrote:
    >>> The "standard" way to iterate over a container should be:
    >>>
    >>> std::vector<int>::iterator iter;
    >>> for (iter=var.begin(); iter!=var.end(); ++iter) {
    >>> ...
    >>>
    >>> }

    > 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 example, right?
    >>> But I always end up using
    >>> for (size_t i=0; i < var.size(); ++i) {
    >>> ...
    >>>
    >>> }


    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.
    Fred Zwarts, Dec 22, 2010
    #8
  9. "Fred Zwarts" <> writes:

    > 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?
    Andrea Crotti, Dec 22, 2010
    #9
  10. Andrea Crotti

    Fred Zwarts Guest

    "Andrea Crotti" <> wrote in message
    news:-aachen.de
    > "Fred Zwarts" <> writes:
    >
    >> 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?


    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.
    Fred Zwarts, Dec 22, 2010
    #10
  11. "Fred Zwarts" <> writes:

    >
    > 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?
    Andrea Crotti, Dec 22, 2010
    #11
  12. Andrea Crotti

    James Kanze Guest

    On Dec 22, 12:53 am, Ian Collins <> wrote:
    > On 12/22/10 01:46 PM, Chris Gordon-Smith wrote:


    > > On Tue, 21 Dec 2010 15:12:49 -0800 (PST), Joshua Maurice<> wrote:
    > >> On Dec 21, 3:09 pm, Andrea Crotti<> wrote:
    > >>> The "standard" way to iterate over a container should be:


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


    > >>> }

    > > 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).


    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
    James Kanze, Dec 22, 2010
    #12
  13. Andrea Crotti

    James Kanze Guest

    On Dec 22, 11:04 am, Andrea Crotti <> wrote:
    > "Fred Zwarts" <> writes:


    > > 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?


    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.)

    --
    James Kanze
    James Kanze, Dec 22, 2010
    #13
  14. Andrea Crotti

    Bo Persson Guest

    Fred Zwarts wrote:
    > "Andrea Crotti" <> wrote in message
    > news:-aachen.de
    >> "Fred Zwarts" <> writes:
    >>
    >>> 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?

    >
    > 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
    Bo Persson, Dec 22, 2010
    #14
  15. Andrea Crotti

    Ian Collins Guest

    On 12/23/10 12:27 AM, James Kanze wrote:
    > On Dec 22, 12:53 am, Ian Collins<> wrote:
    >> On 12/22/10 01:46 PM, Chris Gordon-Smith wrote:

    >
    >>> On Tue, 21 Dec 2010 15:12:49 -0800 (PST), Joshua Maurice<> wrote:
    >>>> On Dec 21, 3:09 pm, Andrea Crotti<> wrote:
    >>>>> The "standard" way to iterate over a container should be:

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

    >
    >>>>> }
    >>> 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).

    >
    > 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.

    --
    Ian Collins
    Ian Collins, Dec 22, 2010
    #15
  16. Andrea Crotti

    James Kanze Guest

    On Dec 22, 6:51 pm, "Bo Persson" <> wrote:
    > 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.

    --
    James Kanze
    James Kanze, Dec 26, 2010
    #16
  17. Andrea Crotti

    Jorgen Grahn Guest

    On Tue, 2010-12-21, Andrea Crotti wrote:
    > 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

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, Dec 30, 2010
    #17
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hendrik Maryns
    Replies:
    18
    Views:
    1,398
  2. greg
    Replies:
    6
    Views:
    444
    Dietmar Kuehl
    Jul 17, 2003
  3. Replies:
    6
    Views:
    626
    Jim Langston
    Oct 30, 2005
  4. Steven D'Aprano

    What makes an iterator an iterator?

    Steven D'Aprano, Apr 18, 2007, in forum: Python
    Replies:
    28
    Views:
    1,128
    Steven D'Aprano
    Apr 20, 2007
  5. Isaac Won
    Replies:
    9
    Views:
    348
    Ulrich Eckhardt
    Mar 4, 2013
Loading...

Share This Page