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

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-08-10 02:43:50

On Friday 10 August 2001 02:21, you wrote:
[snip]
> 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.  

Perhaps the second condition to the statement in table 72 is the most 
important, because it is specifically: "If a==b and (a,b) is in the domain of 
== then *a is equivalent to *b."

For istream_iterator (ignoring implementations and looking only at the 
standard description):
  - any two istream_iterators that reference the same istream are equal based 
on operator==, so consider:
istream_iterators i, j;
j = i;
++i;
i == j; // true, but invalid because (i, j) need not be in the domain of ==

So, *i need not equal *j, and the equivalence condition from table 72 makes 
sense.

  - Now let's ignore the intervening increment: since the "value" member of i 
was initialized during the last increment, j = i will copy that value, so 
*i == *j must be true. Thus, the equivalence condition from table 72 still 
makes sense.

Now istreambuf_iterator:
  - sgetc() will return the same character for the same stream, so (i == j) 
implies *i == *j when i and j reference the same stream buffer. The only 
problem is that i == j if i and j reference different stream buffers. But, 
should (i, j) be in the domain of == if they reference different stream 
buffers? I would think not, so I see no reason that the condition in Table 72 
doesn't hold.
 
>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).

Table 72 explicitly states that the intervening ++ may make j 
nondereferencable and/or make (i, j) not in the domain of ==, so either 
(i == j) is illegal or *j is illegal after the increment. Either way, it is 
not valid to check the equivalence condition from table 72 after you've 
incremented one of the iterators.

> 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

istream_iterator can do precisely this; istreambuf_iterator does not need to 
because the caching is done in the referenced stream buffer.

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

... and they may not be in the domain of == either.
[snip]

Constructing input iterators based on what I believe are the intended 
semantics (and I think are reinforced by the definitions of istream_iterator 
and istreambuf_iterator) is _hard_. For cases where dereferencing may cause 
side effects it is _very_ painful because you can't follow istream_iterator's 
lead by caching the value in operator++ (because side effects would then 
occur even if the iterator was never dereferenced), but if one iterator is 
dereferenced then all equivalent iterators must know about it. The best 
implementation method may very well be to use an implementation as such:

struct some_input_iterator {
  boost::shared_ptr< std::pair<T, bool> > value;

  some_input_iterator() : value(new make_pair(T(), false)) {}
  some_input_iterator(const some_input_iterator& other) : 
    value(other.value) {}

  // same for postincrement
  some_input_iterator& operator++() 
  { 
    value.reset(new make_pair(T(), false)); return *this; 
  }

  some_input_iterator& operator=(const some_input_iterator& other)
  {
    value = other.value;
    return *this;
  }

  const T& operator*() const { 
    if (!value->second) {
      value->first = /* get the value from wherever */
      value->second = true;
    }
    return value->first;
  }
};

The point of the implementation being that each equivalence class of input 
iterators references the same cached data and boolean flag. When an input 
iterator is incremented, it creates its own new equivalence class.

[snip trivia]

        Doug