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

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-08-09 08:42:38

On Thursday 09 August 2001 07:14, you wrote:
> >Going back to the original question, I think it may make sense if the
>
> domain of operator== is considered rather than the result of applying
> it to out of domain iterators.  Consider that there can only be one
> value of an input iterator into whatever it is into.  There may be
> copies of that value, but only one value.  Incrementing any one of
> the copies invalidates all other copies and they are no longer in
> the domain of operator==.  Iterators into different things are not
> in the domain of operator==.
> <
>
> Not just operator++, operator* effectively invalidates all copies of an
> iterator (or at least leaves them in an undefined state), that's why there
> is a requirement that calls to operator* and operator++ must alternate. (OK
> that's not what the standard says - it says that algorithms must be "single
> pass algorithms" and that they can not pass through the same iterator
> twice, dereferencing without incrementing counts as a double pass IMO).
>
> >The value returned by operator== for either of the standard input
> >iterators is basically meaningless except for comparing to the
> >end iterator.
>
> Yep.
>
> >i == i // true
> >*i == *i // true
>
> No, *i gets called twice here, and violates the interface requirements for
> input iterators (that calls to operator* and operator++ alternate), the
> result is undefined.

There was discussion of this in this thread:
http://groups.yahoo.com/group/boost/message/14090

I believe the overall consensus was that operator* should be stable, so the 
above *i == *i is valid. There were a few arguments, though my favorite is 
that the find_if() algorithm's result iterator is useless unless operator* is 
stable:

input_iterator j = std::find_if(i, end, some_predicate);
if (j != end) {
  std::cout << *j << std::endl; /* This violates the interface requirements 
for input iterators, because std::find_if() had to dereference j to determine 
if the predicate was true */

> >j = i;
> >j == i // true
> >*j == *i // true
>
> No, calling *i invalidates j, and vice versa (must be "single pass
> algorithm").

If operator* is stable so that *i == *i, then if i == j, *i is equivalent to 
*j, so you can substitute *j for *i in *i == *i and get *i == *j.

I'm not sure what to think about the note in 24.1.1p3, especially the 
sentence: "Equality does not guarantee the substitution property or 
referential transparency." This seems to say that dereferencing an iterator 
is not stable (as you've said all along).

Personally, I would dereference to be stable (so that find()/find_if() need 
to be changed to use forward iterators) but I would like == to be defined 
only for:
i == i: always true
i == end: true if at end, false otherwise
i == j: always false

This makes it reasonable to implement an input iterator that gets its data 
from a volatile source: it can easily be cached on first access, but you 
don't have to deal with sharing the cache among iterators.

> - John Maddock
> http://ourworld.compuserve.com/homepages/john_maddock/

        Doug