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

From: Corwin Joy (cjoy_at_[hidden])
Date: 2001-08-10 01:21:28

----- Original Message -----
From: "Douglas Gregor" <gregod_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Thursday, August 09, 2001 10:16 PM
Subject: Re: [boost] (infinite) sequences using recurrence relations

<...snip...>
> . Understanding the exact input iterator
> behavior with respect to multiple dereferences and multiple copies of the
> iterator is essential in formulating such an iterator.
>
> The example I'm dealing with: dereferencing an iterator calls a function
> (which may have side effects), and the return value is the result of
> dereferencing the iterator. If dereference and increment must alternate,
then
> construction is trivial: operator* just calls the function. If dereference
> must be stable, the value must be cached. But if dereferencing is stable
> using different copies of equivalent iterators, the cached data must be
> shared by all versions. Consider this code:
>
> input_iterator i = ..., j = ...;
> if (i == j)
>   assert(*i == *j); // ?
>
> If this is true of input iterators, then istreambuf_iterator does not
model
> an input iterator, because of 24.5.3.5p1: "Returns: true if and only if
both
> iterators are at end-of-stream, or neither is at end-of-stream, regardless
> of what streambuf object they use."
>
> Doug

My advice is, again, look at the standard as I suggested in my previous post
on this thread.  Look carefully as table 72 on p. 511 of the standard.  Note
that a == b only implies *a "equivalent" to *b.  As I noted, my
interpretation
based on istream_itreator and istreambuf_iterator is that this equivalence
means
almost nothing as istreambuf_iterator may even be pointing to different
streams
in the case of equality.  Also worth noting, is that the SGI trivial
iterator requirement
is also not satisfied, a == b does not imply &*a == &*b as per
istreambuf_iterator
or just look at the istream iterator code in the SGI library itself.
However,
the more I think about it, the more I am convinced that this is *NOT* a
defect but
actually a deliberate design decision.  Think, for a moment about what it
would
take to make this equality hold for istreambuf iterator implementations
assuming that
a constructed from b implies a == b.

istream_iterator<int> i(cin), j(i);
cout << *i;  // 1
i++;
cout << *j; // 2

Here j is constructed from i, so we should have i == j at line 1.  However,
unless
i caches that value and passes it to j then line 2 may give a different
value
(O.K. i == j implies *i == *j does not mean that *i and *j have to give the
same
values after intervening operations but if they don't it is not a very
useful postcondition).
So, to support *i == *j this almost forces you to fetch a first value for *
at construction time
for an iterator but that also is undesirable in (at least) two ways

1. The underlying input source may not be available at construction time or
you may want a
just-in-time retrieval of that value for other sequencing reasons.

2. Consider the following code:
input_iterator<int> i(cin), j;
j++;
input_iterator<int> k(cin);

Note here that although i and k are both constructed to read from the same
data source (cin), because of
the intervening increment we will likely not have *i == *k.  (Then again,
there is absolutely no requirement
or real reason why two seperately constructed iterators should be equal.  It
just makes == a bit less useful
than you might think.  Also, beware of the "container trap" when building
input_iterators.  If you try to
build them from an artifical container e.g.
input_iterator<int> i = input_iterator_container.begin();
input_iterator<int> j = input_iterator_container.begin();
then users might reasonably expect i ==j which may be hard to support.  I
guess this is just a bit of
warning to always use the direct construction syntax for creating iterators
e.g.: input_iterator<int> i(cin),  and
avoid the trap of building any artificial container to support construction
since this will cause you much
grief later on.)

While I'm on my favorite Jeopardy topic of iterator trivia there is one
other intersting bit to note about these.
In table 72, p. 511 of the standard you will notice something weird about
the postfix increment operator:
Namely, it is specified as (void)r++.
In other words, unlike all other standard iterator types, an input iterator
is not required to return a copy of its old value!
Again, I think this is deliberate since the SGI docs make a big point of
noting (footnote [4] for standard iterators) that
"After executing ++i, it is not required that copies of the old value of i
be dereferenceable or that they be in the domain of operator==."

Part of the motivation for this (obliquely mention in Matt Austern's book)
is, I believe, that they wanted to allow
one to implement input iterators such that for a given input source **there
might be allowed only one actual input iterator
reading from that source**, and all copies of the iterator might actually
point to the same place in the input buffer. Therefore if i++ was forced to
return an old value that was dereferencable this might lead to input
iterators having to support multiple "positions" which I think they wanted
to avoid in the standards specification.

 .