Re: [boost] (infinite) sequences using recurrence relations

From: Corwin Joy (cjoy_at_[hidden])
Date: 2001-08-07 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 random-access 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 non-const 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 end-of-stream or neither is at end-of-stream,  **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 Pac-Man 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