[boost] Re: graph structure interface (proxies and forward iterators)

From: scleary_at_[hidden]
Date: 1999-12-08 09:54:14

Dave wrote:
> Greg wrote:
> > But vector<bool> can't be fixed, and can't be killed either.
>
> I think I disagree with both of those statements (vendors
> just need some hand-holding, so they can see how to accomodate existing
uses of
> vector<bool>), but it's beside the point.
>
> >> >but given that we
> >> >have vector<bool> we will need to fix the ForwardIterator
> >> >requirements so that vector<bool>::interator conforms.  That
> >> >fix might well apply to GGCL iterators.
> >>
> >> Unfortunately, this is impossible. The main reason this iterator
requirements
> >> change will never happen is that relaxing iterator requirements would
remove
> >> guarantees that conforming programs are now allowed to depend upon --
i.e., it
> >> would break a lot of existing code. For example, I know of commercial
> >> implementations of the standard library where some algorithms quite
rightly
> >> assume the T&'s and won't compile with vector<bool>.
> >
> > I don't mind breaking libraries if it will help users, and I suspect
> > that such libraries will eventually cone afoul of their users, if not
> > the standard.
>
> Nobody is suggesting breaking anything. Jeremy's suggestion is to provide
> something which looks very much like an iterator but in fact is not.
Whether
> or not it is worth providing this bit of syntactic sugar at the cost of
> possible confusion and abuse is a question we need to decide.
>
> I'd like to suggest once again that someone rigorously define the
> requirements of a ProxyIterator and ProxyContainer... someone
> who cares about the issue (Greg?). The only way we'll know the
> real-world impact of relaxing the current requirements is if we get some
> experience programming to a different set of requirements.
>

To get Proxy Iterator, just change the iterator requirements' return values
from "T &" to "iterator_traits<X>::reference", where the reference type is
defined to be "an lvalue or rvalue", (modifiable if the iterator is
mutable), leaving what _type_ of value up to the specification of that
particular iterator.  (Notes: "T &" is a modifiable lvalue; "const T &" is a
nonmodifiable lvalue; "vector<bool>::reference" is a modifiable rvalue).

The reason we have to allow rvalues is because "The result of calling a
function [including overloaded operators] that does not return a reference
is an rvalue" (ANSI 3.10p5).

A Proxy Container is just a container that returns Proxy Iterators.

With these definitions, every Input/Fwd/Bi/Rnd Iterator is also a Proxy
Iterator of the same category, and every Standard Container is a Proxy
Container.  The only container in the Standard that is a Proxy Container but
not a Standard Container is "vector<bool>".

However, all non-Boost-aware algorithms that can handle Proxy Iterators
(which in my experience is most of them) can only see our iterators as Input
iterators.  The cleanest solution is, IMO, a change in the Standard.  We can
work around the problem with legacy code expecting "T &" by deriving the
current iterator tags from the proxy iterator tags.

iterator_traits is orthogonal enough; the problem is that Forward Iterator
req's break that orthogonality by requiring "T &" instead of a generic
"reference" type.

Just my two bits.
        -Steve

P.S. I've fooled around with this before, and made a "mayfly_iterator"
class, templated on a Generator and a type, which generates its results on
the fly when dereferenced.  It is basically a generalized proxy iterator.
I've demoted it to "experimental" because of the problems with iterator
tags.  It's a simple class, exactly what you would expect, but I'll post it
if there's interest.

P.P.S. If we're talking about changing the Standard, we should change
Container requirements for "reference" and "const_reference" in a similar
manner.