Re: [boost] Re: Re: Re: Zero Unnecessary Temporary Objects:ARevolution

From: Yitzhak Sapir (yitzhaks_at_[hidden])
Date: 2002-10-14 06:58:41

On Mon, 14 Oct 2002, [Windows-1252] Terje Slettebø wrote:

> >From: "Yitzhak Sapir" <yitzhaks_at_[hidden]>
>
> >Anyway, now, if I write a bidirectional iterator,
> >does a standard bidirectional iterator (ie, a bidirectional iterator as
> >defined by the standard) me to provide such an implementation such that,

That should have said "require me to provide an implementation such that"

> >"if x == end(), and the sequence in question is non empty, --x provides a
> >valid iterator to the element before the end"?
>
> That's how I understand it, yes.
>
> 23/9 says, "If the iterator type of a container belongs to the bidirectional
> or random access iterator categories (24.1), the container is called
> reversible and satisfies the additional requirements in Table 66:"

I read that as a condition for an STL Container.  Any STL container
must meet this requirement.  But my own UserDefinedContainer doesn't have
to.  Neither do iterator adaptors that are not related to containers.

> Among them are:
>
> "a.rbegin()", which should give the effect of "reverse_iterator(end())".

But that's only for an STL Container.  At least I know that --end() is
valid for any STL Container.

> reverse_iterator() takes an iterator in the constructor, and its
> operator++() definition is quoted above, by Dave.

I am not a language lawyer, and I am using the public review document
here, so what I say may not be valid, but since this brought up questions
I had, I'll go further and try to ask more detailed questions regarding
them.  If I err anywhere along the way, sorry :-)

24.4.1/1 seems to claim that all random and bidirectional iterators have
corresponding reverse iterators.  So even a random or bidirectional
iterator that I write will have one.  Now, on a relatively basic level
that is pretty clear.  After all, the reverse_iterator template can be
instantiated for any template parameter and if my class satisfied at least
the bidirectional iterator requirements it will instantiate fine.  But
does this mean also that:
  MyIterator i...
  reverse_iterator(i)
must return a usable reverse iterator for any iterator i in the range
[begin, end] of the iterator's sequence?

Furthermore, using the same logic, it is possible to claim, based on
24.4.1.3.3 (operator* definition for a reverse iterator), which states (in
the document I'm looking at):
  Effects: Iterator tmp = current;
           return *--tmp;
That Iterator may not hold any cached value to the object.  If it did,
this implementation of operator*() wouldn't work (because the cached
reference would be destroyed when Iterator went out of scope in the return
of the operator*()).  By the same logic as above, if reverse_iterator must
return a "valid" iterator (valid here includes an end iterator) for any
"valid" parameter iterator it receives, so too, any possible valid
parameter iterator it receives, cannot hold a cached reference.  Note that
cached pointed-to iterator objects are part of the reasoning and rationale
given for operator[] returning a value_type and not a reference type, in
iterator_adaptors.hpp.  Since operator[] is only a requirement for random
access iterators, if this logic means that all random access iterators
must not hold cached values, operator[]'s main rationale for returning
values as opposed to references (as I understood it) is gone.

I suppose that this would be a much more extreme statement.  Both these
conclusions limit the user drastically.  The bad news is that you can't
have cached objects in iterators, and you can't write end-marker
iterators.  But the good news is that you can write --end() for any end()
iterator.  (What I understood so far is that if it compiles, it is
safe...)

My question then comes down to, and I would thank a language lawyer and
someone who can give me a definitive answer regarding these issues:

Is the statement in 24.4.1/1 simply a statement of the fact that
reverse_iterator is a template that compiles for any bidirectional or
random access iterator, but it says nothing regarding whether the use of
the reverse_iterator template is ok? In that sense, reverse_iterator is
only usable for the iterators that are valid for it, and all STL container
iterators are valid, but user defined iterators may not be.  --end() is
not safe then without guarantees in the non-STL container case, and
neither is reverse_iterator(user_iterator).  But bidirectional and random
access iterators may maintain cached references and they may implement
"end marker" iterators.

Or does it mean that if I write an iterator and expect it to be a valid
bidirectional/random access iterator, it must also be validly usable as a
parameter to reverse iterator?  If it does, do both the above conclusions
hold?  That I must write an end() such that -- is valid and safe for it,
(if it compiles), and that it cannot hold a cached reference (if
*reverse_iterator compiles?)

Have I gone too far here?