[boost] Re: [filesystem + iterator] directory iterator problem

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-04-22 00:57:30

David Abrahams wrote:

>> Let me see. The r++ is required to be:
>>
>>    {
>>        X tmp = r;
>>        ++r;
>>        return tmp;
>>    }
>>
>> After assignment to 'tmp', *tmp returns the right value. After ++r it
>> returns different value.
> 
> Right.  That is intentionally allowed for input iterators, and in fact
> some do work that way.

Could you give some examples? 

>>      pre: a is dereferenceable. If a == b then *a
>>      is equivalent to *b.
> 
> And I don't see how the above relates to this, either.
> 
>> But really, isn't it right to assume that repeating applications of
>> operator* with no ++ in between will return the same value?
> 
> I believe that's guaranteed by the above precondition you cited.

I'm not sure. It's not stated that after 

    X tmp = r;

it's true that "tmp == r". Nor I can find statement that "*tmp is the same
as *r" after assignment. And if it's guaranteed, then "*tmp" should always
return the same value, because tmp itself it not incremented.

>>> b.  the iterator can track whether an iterator returned from a
>>>     post-increment is "active and not yet dereferenced"
>>> 
>>> case b. is interesting; it would mean that operator++(int) can set a
>>> flag telling the iterator to consume another value before
>>> dereferencing.
>>
>> Oh, it can be described as "deferred post-increment", which is actually
>> done only on next deference. But still, won't it reasonable to expect
>> that after the following code:
>>
>>    some_iterator i = ..
>>  
>>    some_iterator p1 = *i;
>                         ^-----you don't mean that, do you?

Yes, I didn't meant '*'.

>>    ++i;
>>    some_iterator p2 = *i;
>>    ++i;
>>    ...
>>    some_iterator pN = *i;
>>
>> all iterators are still return the "right" values?
> 
> I don't think the standard gives you any assurance of that, and in
> fact I doubt that it was intended that input iterators be forced to
> store a value, and in fact note 3 in 24.1.1 seems to confirm my doubt:
>     -3- [Note: For input iterators, a == b does not imply ++a ==
>      ++b. (Equality does not guarantee the substitution property or
>      referential transparency.) Algorithms on input iterators should
>      never attempt to pass through the same iterator twice. They
>      should be single pass algorithms...]

I read it to mean something different: you can't copy single_pass iterator,
increment the original iterator and then take the copy and iterate again.

Let me ask a different question: istream_iterator extracts next item in
operator++ and stores it inside. It it allowed to implement extraction in
operator*(), so that you don't need to store anything at all? I'd say it
would be very confusing behaviour. So, istream_iterator really has to store
value. 

And it seems to me, all single pass iterators have to store the value to
allow for repeated operator*() calls. The only case when it's not needed is
when iterator is a "view" of some other sequence (e.g. filter_iterator).
But then iterator keeps a reference to that other sequence, and I don't see
why copies of iterator can't retain the same value even if origial iterator
is incremented.

- Volodya