Why next/prev for iterators in C++0x?

Discussion in 'C++' started by Scott Meyers, Apr 23, 2011.

  1. Scott Meyers

    Scott Meyers Guest

    I just noticed that the FDIS (and at least some older drafts) includes
    specifications for next and prev funtions on iterators. They're just
    shorthands for calls to advance:

    template <class ForwardIterator>
    ForwardIterator next(ForwardIterator x,
    typename std::iterator_traits<ForwardIterator>::difference_type n = 1);

    Effects: Equivalent to advance(x, n); return x;


    template <class BidirectionalIterator>
    BidirectionalIterator prev(BidirectionalIterator x,
    typename std::iterator_traits<BidirectionalIterator>::difference_type n
    = 1);

    Effects: Equivalent to advance(x, -n); return x;

    Does anybody happen to know the motivation for putting these functions
    in the new standard?

    Thanks,

    Scott

    --
    * C++ and Beyond: Meyers, Sutter, & Alexandrescu, Aug 7-10 in Banff
    (http://cppandbeyond.com/)
     
    Scott Meyers, Apr 23, 2011
    #1
    1. Advertising

  2. Scott Meyers wrote, On 23.4.2011 20:16:
    > I just noticed that the FDIS (and at least some older drafts) includes
    > specifications for next and prev funtions on iterators. They're just
    > shorthands for calls to advance:
    >
    > [...]
    >
    > Does anybody happen to know the motivation for putting these functions in the
    > new standard?

    Aren't those the work horse of the for(T x: collection) statement?

    --
    VH
     
    Vaclav Haisman, Apr 23, 2011
    #2
    1. Advertising

  3. Scott Meyers

    Scott Meyers Guest

    On 4/23/2011 11:31 AM, Vaclav Haisman wrote:
    > Aren't those the work horse of the for(T x: collection) statement?


    Nope, that relies on the ++ operator. Details in FDIS 6.5.4/1. From
    what I can tell, there are zero uses of prev and next on iterators in
    the FDIS.

    Scott

    --
    * C++ and Beyond: Meyers, Sutter, & Alexandrescu, Aug 7-10 in Banff
    (http://cppandbeyond.com/)
     
    Scott Meyers, Apr 23, 2011
    #3
  4. Scott Meyers

    Marc Guest

    Scott Meyers wrote:

    > I just noticed that the FDIS (and at least some older drafts) includes
    > specifications for next and prev funtions on iterators. They're just
    > shorthands for calls to advance:
    >
    > template <class ForwardIterator>
    > ForwardIterator next(ForwardIterator x,
    > typename std::iterator_traits<ForwardIterator>::difference_type n = 1);
    >
    > Effects: Equivalent to advance(x, n); return x;

    [...]
    > Does anybody happen to know the motivation for putting these functions
    > in the new standard?


    advance modifies its argument, whereas next(it) is a version of it+1
    that works with more general iterators. To emulate next with advance,
    you actually need to first copy the iterator, which can be
    inconvenient. I can for instance access the last element of a sequence
    through *prev(end(sequence)) in line instead of declaring:
    auto iter_end=end(sequence); --iter_end;
    ....expression using *iter_end...

    The boost prior/next functions are used quite a bit and a proof that
    this is convenient.
     
    Marc, Apr 23, 2011
    #4
  5. Scott Meyers

    Scott Meyers Guest

    On 4/23/2011 2:53 PM, Marc wrote:
    > advance modifies its argument, whereas next(it) is a version of it+1
    > that works with more general iterators. To emulate next with advance,
    > you actually need to first copy the iterator, which can be
    > inconvenient. I can for instance access the last element of a sequence
    > through *prev(end(sequence)) in line instead of declaring:
    > auto iter_end=end(sequence); --iter_end;
    > ...expression using *iter_end...
    >
    > The boost prior/next functions are used quite a bit and a proof that
    > this is convenient.


    Thanks for the explanation.

    Scott
    --
    * C++ and Beyond: Meyers, Sutter, & Alexandrescu, Aug 7-10 in Banff
    (http://cppandbeyond.com/)
     
    Scott Meyers, Apr 23, 2011
    #5
  6. On Apr 23, 5:53 pm, Marc <> wrote:
    > Scott Meyers  wrote:
    > > I just noticed that the FDIS (and at least some older drafts) includes
    > > specifications for next and prev funtions on iterators.  They're just
    > > shorthands for calls to advance:

    >
    > > template <class ForwardIterator>
    > > ForwardIterator next(ForwardIterator x,
    > > typename std::iterator_traits<ForwardIterator>::difference_type n = 1);

    >
    > > Effects: Equivalent to advance(x, n); return x;

    > [...]
    > > Does anybody happen to know the motivation for putting these functions
    > > in the new standard?

    >
    > advance modifies its argument, whereas next(it) is a version of it+1
    > that works with more general iterators. To emulate next with advance,
    > you actually need to first copy the iterator, which can be
    > inconvenient. I can for instance access the last element of a sequence
    > through *prev(end(sequence)) in line instead of declaring:
    > auto iter_end=end(sequence); --iter_end;
    > ...expression using *iter_end...
    >
    > The boost prior/next functions are used quite a bit and a proof that
    > this is convenient.


    I must adamantly agree. I've found that I've rarely used advance, but
    jump at the chance to use next. At least for me, my use cases
    commonly need both the iterator being advanced from, and the advanced
    iterator, later in the logic. And while it is easy enough to copy the
    iterator being advanced from and then advance it, it is just
    delightful to do those two steps in just one with next. There's just
    so many contexts where one step works and two don't (example snippet
    from my own code):

    ...
    for (ForwardIterator1 j = std::next(i); j != last1; ++j)
    if (pred(*i, *j))
    ++c1;
    ...

    Howard
     
    Howard Hinnant, Apr 24, 2011
    #6
  7. Scott Meyers

    crea Guest

    "Howard Hinnant" <> wrote in message
    news:...
    On Apr 23, 5:53 pm, Marc <> wrote:

    " ...
    for (ForwardIterator1 j = std::next(i); j != last1; ++j)
    if (pred(*i, *j))
    ++c1;
    "

    Just a small comment: I just read an article to say , that we dont really
    (always) need to do ++j, but can do j++. The reason is that the computer can
    trim the code many times when it compiles. Also testing showed that there
    was no big difference even if j++ was used. But I have to read the article
    again...
    On the other hand, I dont know why using ++j would be not good.
     
    crea, Apr 24, 2011
    #7
  8. * crea, on 24.04.2011 10:02:
    > "Howard Hinnant"<> wrote in message
    > news:...
    > On Apr 23, 5:53 pm, Marc<> wrote:
    >
    > " ...
    > for (ForwardIterator1 j = std::next(i); j != last1; ++j)
    > if (pred(*i, *j))
    > ++c1;
    > "
    >
    > Just a small comment: I just read an article to say , that we dont really
    > (always) need to do ++j, but can do j++. The reason is that the computer can
    > trim the code many times when it compiles. Also testing showed that there
    > was no big difference even if j++ was used. But I have to read the article
    > again...
    > On the other hand, I dont know why using ++j would be not good.


    For the built-in operators the only difference is (in general) that writing
    "++j" states just what you want, while "j++" adds a meaningless request.

    The standard library's iterators all support "j++" with reasonable semantics.
    The basis is the last row of table 72 in C++98 §24.1.1/2. However, although a
    smart compiler will probably optimize the implied creation of some expression
    result object, this is not necessarily so for non-standard iterators.

    Also, a non-standard iterator may simply not provide "j++" (after all there's
    seldom any good reason to use it), and so at least templated code can be more
    generally useable if it does not rely on iterators providing "j++".

    And then, when you have adopted the notation "++j" for iterators in general,
    it's just as well to do so also for raw pointers, yielding the C++ convention of
    writing "++j" by default, reserving the postfix form for where it's needed.

    The pressures work the other way for C programming. In C there are only raw
    pointers. And there is a tradition, all the way back to K&R, of writing "j++",
    so in C it can be most natural to write "j++" by default.


    Cheers & hth.,

    - Alf

    --
    blog at <url: http://alfps.wordpress.com>
     
    Alf P. Steinbach /Usenet, Apr 24, 2011
    #8
  9. Scott Meyers

    James Kanze Guest

    On Apr 24, 9:02 am, "crea" <> wrote:
    > "Howard Hinnant" <> wrote in message


    > news:...
    > On Apr 23, 5:53 pm, Marc <> wrote:


    > " ...
    > for (ForwardIterator1 j = std::next(i); j != last1; ++j)
    > if (pred(*i, *j))
    > ++c1;
    > "


    > Just a small comment: I just read an article to say , that we
    > dont really (always) need to do ++j, but can do j++. The
    > reason is that the computer can trim the code many times when
    > it compiles. Also testing showed that there was no big
    > difference even if j++ was used. But I have to read the
    > article again...
    > On the other hand, I dont know why using ++j would be not good.


    In practice, there's no valid technical reason for preferring
    one over the other---it's just a question of which one you like
    best. Politically speaking, however... some noted authors have
    claimed otherwise, and have influences a large number of
    programmers; it's easier to just use ++j than to argue with
    them. (FWIW: K&R favored j++, and at least in the earlier
    versions of his books, so did Stroustrup, so for older
    programmers, who learned from the original masters, j++ often
    seems more natural. Just because we've seen it more often,
    however; not for any technical reason.)

    --
    James Kanze
     
    James Kanze, Apr 25, 2011
    #9
  10. Sprechen sie C++, Apr 26, 2011
    #10
  11. Scott Meyers

    Jorgen Grahn Guest

    On Mon, 2011-04-25, James Kanze wrote:
    > On Apr 24, 9:02 am, "crea" <> wrote:
    >> "Howard Hinnant" <> wrote in message

    >
    >> news:...
    >> On Apr 23, 5:53 pm, Marc <> wrote:

    >
    >> " ...
    >> for (ForwardIterator1 j = std::next(i); j != last1; ++j)
    >> if (pred(*i, *j))
    >> ++c1;
    >> "

    >
    >> Just a small comment: I just read an article to say , that we
    >> dont really (always) need to do ++j, but can do j++. The
    >> reason is that the computer can trim the code many times when
    >> it compiles. Also testing showed that there was no big
    >> difference even if j++ was used. But I have to read the
    >> article again...
    >> On the other hand, I dont know why using ++j would be not good.

    >
    > In practice, there's no valid technical reason for preferring
    > one over the other---it's just a question of which one you like
    > best. Politically speaking, however... some noted authors have
    > claimed otherwise, and have influences a large number of
    > programmers; it's easier to just use ++j than to argue with
    > them. (FWIW: K&R favored j++, and at least in the earlier
    > versions of his books, so did Stroustrup, so for older
    > programmers, who learned from the original masters, j++ often
    > seems more natural. Just because we've seen it more often,
    > however; not for any technical reason.)


    So what about the argument that j++ can be a lot slower for
    user-defined overloadings? Is that just politics, no longer true,
    irrelevant, or ... ?

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
     
    Jorgen Grahn, Apr 27, 2011
    #11
  12. Scott Meyers

    Kai-Uwe Bux Guest

    Jorgen Grahn wrote:

    > On Mon, 2011-04-25, James Kanze wrote:
    >> On Apr 24, 9:02 am, "crea" <> wrote:
    >>> "Howard Hinnant" <> wrote in message

    >>
    >>> news:c3808703-28c5-457e-

    ...
    >>> On Apr 23, 5:53 pm, Marc <> wrote:

    >>
    >>> " ...
    >>> for (ForwardIterator1 j = std::next(i); j != last1; ++j)
    >>> if (pred(*i, *j))
    >>> ++c1;
    >>> "

    >>
    >>> Just a small comment: I just read an article to say , that we
    >>> dont really (always) need to do ++j, but can do j++. The
    >>> reason is that the computer can trim the code many times when
    >>> it compiles. Also testing showed that there was no big
    >>> difference even if j++ was used. But I have to read the
    >>> article again...
    >>> On the other hand, I dont know why using ++j would be not good.

    >>
    >> In practice, there's no valid technical reason for preferring
    >> one over the other---it's just a question of which one you like
    >> best. Politically speaking, however... some noted authors have
    >> claimed otherwise, and have influences a large number of
    >> programmers; it's easier to just use ++j than to argue with
    >> them. (FWIW: K&R favored j++, and at least in the earlier
    >> versions of his books, so did Stroustrup, so for older
    >> programmers, who learned from the original masters, j++ often
    >> seems more natural. Just because we've seen it more often,
    >> however; not for any technical reason.)

    >
    > So what about the argument that j++ can be a lot slower for
    > user-defined overloadings? Is that just politics, no longer true,
    > irrelevant, or ... ?


    To me, that argument _always_ sounded like premature optimization. I wonder
    whether it has ever been substantiated by measurements. I also wonder if
    there are any _recent_ measurement supporting that notion: after all,
    improvements in compiler technology may have rendered this worry obsolete.
    (And I would not be surprised if those improvements have been around for
    some 30 years :)


    Best,

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Apr 27, 2011
    #12
  13. Scott Meyers

    SG Guest

    On 27 Apr., 10:04, Kai-Uwe Bux wrote:
    > Jorgen Grahn wrote:
    > > > [...]

    > > So what about the argument that j++ can be a lot slower for
    > > user-defined overloadings?  Is that just politics, no longer true,
    > > irrelevant, or ... ?

    >
    > To me, that argument _always_ sounded like premature optimization.


    Depends on how you define premature optimization. I have no problem
    with writing "++j" instead of "j++" in the first place. It doesn't
    take _any_ more effort, obviously. And since I spend no extra time on
    this "optimization" it also does not have to pay off. So, in the worst
    case I lost nothing and gained nothing. For me "premature
    optimization" implies that the time one spends optimizing will not pay
    off.

    > I also wonder if
    > there are any _recent_ measurement supporting that notion: after all,
    > improvements in compiler technology may have rendered this worry obsolete..


    In case of a UDT that is trivially copyable and has an inline post-
    increment operator, I can imagine that compilers might be smart enough
    to optimize an unnecessary copy away.

    SG
     
    SG, Apr 27, 2011
    #13
  14. Scott Meyers

    Jorgen Grahn Guest

    On Wed, 2011-04-27, SG wrote:
    > On 27 Apr., 10:04, Kai-Uwe Bux wrote:
    >> Jorgen Grahn wrote:
    >> > > [...]
    >> > So what about the argument that j++ can be a lot slower for
    >> > user-defined overloadings?  Is that just politics, no longer true,
    >> > irrelevant, or ... ?

    >>
    >> To me, that argument _always_ sounded like premature optimization.

    >
    > Depends on how you define premature optimization. I have no problem
    > with writing "++j" instead of "j++" in the first place. It doesn't
    > take _any_ more effort, obviously.


    Personally, I still find ++j much uglier than j++ [1], so if someone can
    convince me that I can stop using the ++j idiom I gladly will. But I
    need to be convinced first.

    I can't see how a compiler can magically optimize this in the general
    case, and I can't see how you can prove that the performance loss is
    always negligable. This is the kind of thing you do thousands of times
    in tight loops, like the ones in <algorithm> ...

    Perhaps I misinterpreted what Kanze wrote.

    /Jorgen
    [1] No rational reasons for this, just too many years doing C.

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
     
    Jorgen Grahn, Apr 27, 2011
    #14
  15. Scott Meyers

    Bo Persson Guest

    Jorgen Grahn wrote:
    > On Wed, 2011-04-27, SG wrote:
    >> On 27 Apr., 10:04, Kai-Uwe Bux wrote:
    >>> Jorgen Grahn wrote:
    >>>>> [...]
    >>>> So what about the argument that j++ can be a lot slower for
    >>>> user-defined overloadings? Is that just politics, no longer true,
    >>>> irrelevant, or ... ?
    >>>
    >>> To me, that argument _always_ sounded like premature optimization.

    >>
    >> Depends on how you define premature optimization. I have no problem
    >> with writing "++j" instead of "j++" in the first place. It doesn't
    >> take _any_ more effort, obviously.

    >
    > Personally, I still find ++j much uglier than j++ [1], so if
    > someone can convince me that I can stop using the ++j idiom I
    > gladly will. But I need to be convinced first.
    >
    > I can't see how a compiler can magically optimize this in the
    > general case, and I can't see how you can prove that the
    > performance loss is always negligable. This is the kind of thing
    > you do thousands of times in tight loops, like the ones in
    > <algorithm> ...
    >


    The general idea is that an iterator is a light weight, cheap to copy
    object. That's one reason for the <algorithm>s to pass iterators by
    value.

    And in *most* cases, the compiler will be able so see through the
    temporary copy created by the post increment, and notice that it is
    never used and has no side effects.

    The "general case" is harder, but presumable also less frequent.


    Bo Persson
     
    Bo Persson, Apr 27, 2011
    #15
  16. Scott Meyers

    Öö Tiib Guest

    On Apr 27, 2:33 pm, Jorgen Grahn <> wrote:
    > On Wed, 2011-04-27, SG wrote:
    > > On 27 Apr., 10:04, Kai-Uwe Bux wrote:
    > >> Jorgen Grahn wrote:
    > >> > > [...]
    > >> > So what about the argument that j++ can be a lot slower for
    > >> > user-defined overloadings?  Is that just politics, no longer true,
    > >> > irrelevant, or ... ?

    >
    > >> To me, that argument _always_ sounded like premature optimization.

    >
    > > Depends on how you define premature optimization. I have no problem
    > > with writing "++j" instead of "j++" in the first place. It doesn't
    > > take _any_ more effort, obviously.

    >
    > Personally, I still find ++j much uglier than j++ [1], so if someone can
    > convince me that I can stop using the ++j idiom I gladly will. But I
    > need to be convinced first.


    I don't see the aesthetics. Perhaps i don't have taste of art. Both
    are easy and short to type. It is easy to think of ++j as "increment
    j". So it is easy to read and to think of it too.

    How to think of j++? "j and then increment"? "increment j and tell
    what it was before"? I mostly avoid it because i can't find good
    mental image for postfix operator ++.

    > I can't see how a compiler can magically optimize this in the general
    > case, and I can't see how you can prove that the performance loss is
    > always negligable. This is the kind of thing you do thousands of times
    > in tight loops, like the ones in <algorithm> ...
    >
    > Perhaps I misinterpreted what Kanze wrote.


    Compilers impress these days and discard most code that does not
    affect program's observable behavior. If j++ is less error prone and
    confusing for your team to read than ++j then you should agree to
    prefer it.
    For me it is other way around.
     
    Öö Tiib, Apr 27, 2011
    #16
  17. Scott Meyers

    Jorgen Grahn Guest

    On Wed, 2011-04-27, Bo Persson wrote:
    > Jorgen Grahn wrote:
    >> On Wed, 2011-04-27, SG wrote:
    >>> On 27 Apr., 10:04, Kai-Uwe Bux wrote:
    >>>> Jorgen Grahn wrote:
    >>>>>> [...]
    >>>>> So what about the argument that j++ can be a lot slower for
    >>>>> user-defined overloadings? Is that just politics, no longer true,
    >>>>> irrelevant, or ... ?
    >>>>
    >>>> To me, that argument _always_ sounded like premature optimization.
    >>>
    >>> Depends on how you define premature optimization. I have no problem
    >>> with writing "++j" instead of "j++" in the first place. It doesn't
    >>> take _any_ more effort, obviously.

    >>
    >> Personally, I still find ++j much uglier than j++ [1], so if
    >> someone can convince me that I can stop using the ++j idiom I
    >> gladly will. But I need to be convinced first.
    >>
    >> I can't see how a compiler can magically optimize this in the
    >> general case, and I can't see how you can prove that the
    >> performance loss is always negligable. This is the kind of thing
    >> you do thousands of times in tight loops, like the ones in
    >> <algorithm> ...
    >>

    >
    > The general idea is that an iterator is a light weight, cheap to copy
    > object. That's one reason for the <algorithm>s to pass iterators by
    > value.
    >
    > And in *most* cases, the compiler will be able so see through the
    > temporary copy created by the post increment, and notice that it is
    > never used and has no side effects.
    >
    > The "general case" is harder, but presumable also less frequent.


    And if I have a heavy-weight j++ which doesn't inline, that means I'm
    already in conflict with <algorithm>. Yes, I can buy that argument.

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
     
    Jorgen Grahn, Apr 28, 2011
    #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. Stanley

    Calendar Prev/Next Month

    Stanley, Aug 29, 2003, in forum: ASP .Net
    Replies:
    1
    Views:
    402
    Tommy
    Aug 29, 2003
  2. =?Utf-8?B?UkY=?=

    Next/Prev Year in VS.Net Calendar Control

    =?Utf-8?B?UkY=?=, Jun 3, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    452
    =?Utf-8?B?UkY=?=
    Jun 3, 2004
  3. =?Utf-8?B?UkI=?=
    Replies:
    2
    Views:
    2,293
    =?Utf-8?B?UkI=?=
    Oct 14, 2004
  4. Darren
    Replies:
    3
    Views:
    534
    Darren
    Jun 22, 2005
  5. Mr. SweatyFinger
    Replies:
    2
    Views:
    1,966
    Smokey Grindel
    Dec 2, 2006
Loading...

Share This Page