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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-04-21 07:24:26

David Abrahams wrote:

>> The filesystem lib sources contain the following comment:
>>
>>     The *r++ requirement doesn't appear to apply to the new
>>      single_pass_traversal category
>>      Thus I'm leaving the proxy out pending confirmation from the N1477
>>      authors
> 
> I'm kinda surprised that nobody asked us about that problem; we can't
> confirm something we don't know about!

It was not me who hasn't asked ;-)

>> I'm not sure I understand that. It seems that *r++ should work,
>> since signle pass iterator requires that r++ should work and return
>> object of type X (call it r2), and the reabable iterator requires
>> that *r2 should work. Am I wrong?
> 
> The question is, what are the semantics?
> 
> Input iterator requirements say:
> 
>     Expression    Type    Semantics
>     ----------    ----    ------------------------------
>     (void)r++             equivalent to (void)++r
>     *r++          T       { T tmp = *r; ++r; return tmp; }
> 
> But we don't have anything similar in the new concepts.  I guess
> that's because we're trying to orthogonalize access and traversal, but
> that may not be possible in this case.  If we don't define the
> semantics of *r++, a single-pass iterator is free to implement the
> semantics of *r++ as equivalent to *++r, which is what
> directory_iterator is doing.

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. Well, while it seems intuitive that 'tmp' is
always equal to itself and so *tmp should be always equivivalent to *tmp, I
agree that this is very loose interpretation of

     pre: a is dereferenceable. If a == b then *a
     is equivalent to *b.

But really, isn't it right to assume that repeating applications of
operator* with no ++ in between will return the same value? 

> I'm sure directory_iterator is reporting that its category is
> input_iterator_tag, so I guess we have a problem in the new iterator
> concepts and in the iterator_facade implementation here.
> 
>> And BTW, don't the above requirements
> 
> Which ones?

The requirent that return type of r++ should be X (in Incrementable
iterator).

>> mean r++ cannot return a proxy object, but only a real copy of the
>> iterator?
> 
> The input iterator requirements seem to imply that, for true
> single-pass sequences like streams, either:
> 
> a.  the iterator can store a copy of its value_type so that the
>     iterator returned from r++ can still return the 'tmp' value
>     indicated above when dereferenced
> 
> 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;
   ++i;
   some_iterator p2 = *i;
   ++i;
   ...
   some_iterator pN = *i;

all iterators are still return the "right" values?

- Volodya