Boost logo

Boost :

From: David Abrahams (dave_at_[hidden])
Date: 2004-04-21 09:57:52

Vladimir Prus <ghost_at_[hidden]> writes:

> David Abrahams wrote:
>> 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.

Right. That is intentionally allowed for input iterators, and in fact
some do work that way.

> Well, while it seems intuitive that 'tmp' is always equal to itself
> and so *tmp should be always equivivalent to *tmp

I don't understand what any of that means. Maybe I'm just confused
because it's just too obvious a tautology.

> I agree that this is very loose interpretation of
> 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 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?

That's right.

>> 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;
                        ^-----you don't mean that, do you?
> ++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...]

Dave Abrahams
Boost Consulting

Boost list run by bdawes at, gregod at, cpdaniel at, john at