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

From: David Abrahams (dave_at_[hidden])
Date: 2004-04-26 09:10:43

Vladimir Prus <ghost_at_[hidden]> writes:

> David Abrahams wrote:
>
>>>> Well, I may have been wrong.  The forward iterator requirements say:
>>>> 
>>>>   expression  operational semantics   assertion
>>>>   ----------  ---------------------   ---------
>>>>   ++r                                 r == s and r is dereferenceable
>>>>                                       implies ++r == ++s .
>>>> 
>>>> 
>>>>   X u(a);     X u; u = a;             post: u == a .
>>>
>>> Oh, yea. Together with requirement that "r == s" implies "*r == *s" it
>>> seems to guarantee that ++ does not invalidate copies.
>> 
>> I don't think you need that other requirement.  Remember, an invalid
>> iterator can't be incremented.  So if r is dereferenceable, it's
>> valid. You're still allowed to increment s (a copy of r) after r is
>> incremented, so it can't have been invalidated by incrementing r.
>> 
>> If you're interested in *referent stability* of copies of r, 
>
> What's 'referent stability'?

the stability of "what's referred to" by the iterator.

>> I'm not
>> sure that anything guarantees it.  In other words, nothing guarantees
>> that t is valid after:
>> 
>>     T& t = *r++;
>> 
>> Indeed, some forward iterators actually store the value_type object
>> that they reference.
>
> Yes, that's okay. The property I was asking about is that in the following
> code:
>
>     X it = ...
>     X c = it;
>     *it;
>     ++it;
>     *c;
>
> the values returned by both operator*() calls are the same. 
>
> I always had assumption that for std::forward_iterator this is true.
> Unfortunately, after 20 mins of looking at the requirements I can't prove
> that, gotta take a second look.

OK.

>>> BTW, do new iterator requirement state that iterator type X is
>>> interoperable with itself?
>> 
>> Not explicitly, but that is certainly a logical implication of the
>> requirements on single pass iterators.
>
> How? I can't decude that from any of singla pass iterator requirements.

Incrementable iterator is a refinement of Assignable and Copy
Constructible, and == is an equivalence relation, etc.

>>> but it that I'm not sure what operator++(int) should return...
>
> That's the important question. Writable non-lvalue iterator cannot return a
> proxy storing the value inside, since there's no value to store. So making
> iterator_facade return proxy with stored value for all non-lvalue iterators
> is too simple solution :-(

Ugh, right.  I'll try to discuss this stuff with Jeremy when I see him
tomorrow.

>>>> Thanks for your attention to this; it makes a big difference!
>>>
>>> You're welcome. In fact, I only now understood how complex iterators are
>>> -- due to this discussion and a couple of other iterator-releated issued
>>> I had today. It's really good there are formal requirements.
>> 
>> Yeah.  Well, the ones in the standard a sort of a mess, which makes
>> writing backward-compatible "new requirements" a lot harder than it
>> would otherwise be.
>
> At least, there are requirements, which makes it possible to say "your
> iterator violates standard requirements", which is much better that "your
> iterator is strange" ;-)

Definitely.

-- 
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com