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

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-08-10 15:03:32

On Friday 10 August 2001 02:57, you wrote:
> On Fri, 10 Aug 2001, Douglas Gregor wrote:
> > 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_.
>
> It does not seem difficult to me.  Istream iterators must be buffered
> and operator* must be stable.  The only problem is making *it++ work.
> The standard gives two examples using an internal buffer and a proxy.

istream_iterator is easy because operator++ can cache the value, and the 
semantics work nicely from there. But I'm considering classes of iterators 
where caching the value before dereference causes side effects that otherwise 
should not occur. Then implementation gets more complicated.

> > For cases where dereferencing may cause
> > side effects it is _very_ painful because
>
> You are violating the concept of an iterator being a pointer into
> some sequence.  I think that the designers of the STL understood
> this problem and created generators as an alternative to iterators.

Not necessarily. A sequence exists, but it is a sequence such that reading it 
destroys it, so caution must be exercised. 

> > struct some_input_iterator {
> >   boost::shared_ptr< std::pair<T, bool> > value;
> >
> >   some_input_iterator() : value(new make_pair(T(), false)) {}
>
> Is this an end iterator?  If not, how do I create a range?  Algorithms
> need ranges and iterators exist for algorithms.
>
> >   some_input_iterator(const some_input_iterator& other) :
> >     value(other.value) {}
>
> This is the copy ctor.  If the above is an end iterator, how do I
> get a begin iterator?
>
> >   some_input_iterator& operator++()
> >   {
> >     value.reset(new make_pair(T(), false)); return *this;
> >   }
>
> Assuming that I can get a begin and end iterator, does the distance
> algorithm give the correct result?  Does it even terminate?

The code posted is more along the lines of an iterator adaptor. Consider the 
transform_iterator_adaptor from the iterator adaptors library, but with a 
function object that has side effects. operator* must be stable, so we have 
to cache the value. The some_input_iterator code posted is a skeletal 
description of how one would make transform_iterator_adaptor conform to the 
input iterator concept regardless of any side effects due to calling the 
function.

> I really think the problem is in trying to claim that something
> which does not iterate through a sequence is an iterator.  Having
> one of those things may be quite useful; however, there is no
> need to try to distort the iterator concept to make it fit or
> to claim that it is an iterator.

It is most definitely a sequence that we are dealing with, and the resulting 
iterator conforms to the input iterator concept. The sequence is the ordered 
application of a function object (with side effects) to the elements of some 
underlying sequence.

> Another support for stable operator* is the merge algorithm.  Do
> you think that the standard intended to require internal buffers
> for the two ranges?  I would prefer avoiding the extra copy.
>
> John

I think we all agree on stable operator*.

        Doug