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

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-08-06 18:38:51

Dave wrote:
> 
> 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.
The reason is that

        assert(i==j); // assumption
        *i = x;
        assert(*i == *j); // conclusion must be provable

and it follows that *i must be a raw reference to a
location shared by all iterators denoting the same
container element, that is, 

        &*i

must be a 'pointer into a container', more formally

        &*i == &*j

The proof rests on i,j being _output_ as well as
forward, and depends on the non-const version
of operator* being called: the result does not
follow for const versions of operator *,
and it doesn't follow if the iterators are not
output (so that there is no requirement to support
writing through a reference).

The proof basically says: if the conclusion
ISN'T derivable, then STL is useless, since
writes to containers need not be reflected on
subsequent reads. So if the conclusion
cannot be deduced, then it is a Defect in the Standard.
If there's any doubt, the Standard is Unclear,
which is also a Defect. :-)

-- 
John (Max) Skaller, mailto:skaller_at_[hidden] 
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
New generation programming language Felix  http://felix.sourceforge.net
Literate Programming tool Interscript     
http://Interscript.sourceforge.net