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

S

Scott Meyers

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
 
V

Vaclav Haisman

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

Scott Meyers

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
 
M

Marc

Scott said:
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.
 
S

Scott Meyers

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
 
H

Howard Hinnant

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
 
C

crea

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

Alf P. Steinbach /Usenet

* crea, on 24.04.2011 10:02:
" ...
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
 
J

James Kanze

"Howard Hinnant" <[email protected]> wrote in message
On Apr 23, 5:53 pm, Marc <[email protected]> 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.)
 
J

Jorgen Grahn

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
 
K

Kai-Uwe Bux

Jorgen said:
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
 
S

SG

Jorgen said:
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
 
J

Jorgen Grahn

Jorgen said:
[...]
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.
 
B

Bo Persson

Jorgen said:
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
 
Ö

Öö Tiib

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

Jorgen Grahn

Jorgen said:
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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top