
Boost : 
From: Corwin Joy (cjoy_at_[hidden])
Date: 20010807 02:00:10
 Original Message 
From: "John Max Skaller" <skaller_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, August 06, 2001 6:38 PM
Subject: Re: [boost] (infinite) sequences using recurrence relations
> > David Abrahams wrote:
> > > Doesn't a range of STL input iterators model a mathematical sequence?
> > > These don't have to be stored in memory all at once. In fact, that's
also
> > > true of bidirectional and randomaccess iterators, since they are
allowed to
> > > cache their lvalue internally. Do we need a new concept?
> >
> > One factor is whether the Standard requires that:
> >
> > Given iterators i, j:
> > i == j implies and requires &*i == &*j
> >
> > Some folks think the wording of the Standard requires this.
> > Other folks think the same wording does not require it.
>
> It doesn't matter what the Standard says about it:
> you can deduce that
>
> i,j forward and output implies &*i == &*j
>
> provided the RHS is well defined AND i,j are nonconst lvalues.
Can you give a more rigorous proof of this. The one you gave failed to
convince me. Also, it is worth emphasizing that the above invariant does
*not* necessarily hold when looking at input iterators. Here is a post I
put out on this to comp.std.c++ a couple of days ago:
I'm trying to understand the input iterator invariants given by the
standard. Specifically, what I am struggling with is section 24.1.1 table
72, p. 511. Here it is stated under the operation *a for the post
conditions: "If a==b and (a,b) is in the domain of == then *a is equivalent
to *b". Note here that the standard does not state that *a == *b as it does
for other iterator types and in fact we can have
i == j but NOT *i == *j as shown by input iterators such as istream_iterator
and istreambuf_iterator, e.g.
#include <iostream>
#include <iterator>
using namespace std;
int main() {
istream_iterator<int> i(cin), j;
j = i;
cout << *i << ", " << *j << endl;
j++;
cout << *i << ", " << *j << endl;
if (i == j)
cout << "i == j is true" << endl;
else
cout << "i == j is false" << endl;
return 0;
}
If I give as input e.g. 2<ret> 3<ret> (to MSVC 6) I get
2, 2
2, 3
i == j is true.
Which I believe is correct because of the standard 24.5.1.2 line 6 p. 530
which states that i == j will return true as long as both istream_iterators
point to the same stream. (I believe they also both have to not be at end()
but I can't find where it says this right now.)
Another example of this kind of thing can be found with istreambuf_iterator
24.5.3.5 p.533 where we have that two istreambuf_iterators are equal iff
both are at endofstream or neither is at endofstream, **regardless of
what streambuf object they use**.
So, back to my question(s)
1. If i == j for an input iterator, what, if anything does it say about the
relationship between *i and *j. (Given istreambuf_iterator it seems to me
that *i and *j may be quite unrelated objects.)
2. Are there STL algorithms that take Input Iterators which make crucial use
of i == j implies *i and *j 'equivalent' (whatever 'equivalent' means
here)?
Dazed, or 'equivalently' confused,
Corwin
 "Computer games doesn't affect kids; I mean if PacMan affected us as kids, we'd all be running around darkened rooms, munching magic pills and listening to repetitive electronic music." Kristian Wilson, Nintendo, Inc. 1989
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk