Re: [boost] improved iterator traits/concepts

From: John E. Potter (jpotter_at_[hidden])
Date: 2001-03-21 05:09:34

On Mon, 19 Mar 2001, Jeremy Siek wrote:

> A little while back I posted about what an improved set of iterator
> concepts and traits would look like, specifically, to solve the problem of
> iterator category and dereference return type semantics being tied into
> the same hierarchy.
> 
> http://groups.yahoo.com/group/boost/message/7832?source=1
> 
> While working on the iterator adaptor library, it has become even more
> apparent to me that the current state of affairs is not acceptable and we
> need a solution sooner than later. For example, there are important
> classes of iterators that you currently can not build with
> iterator_adaptor, like random-access iterators that don't return true
> reference types.
> 
> As a result, I've coded up a new iterator_traits class that replaces the
> iterator_category with traversal_category and return_category.
> 
> An important characteristic of this new iterator_traits class is that it
> is BACKWARD COMPATIBLE, meaning that any iterator for which there is a
> valid std::iterator_traits defined, will also automatically have a valid
> boost::iterator_traits defined.
> 
> I've checked the code and docs into CVS, development/iterator/.
> It currently works with g++, KCC, and VC++, but not Borland.
> 
> A next step would be to provide alternate implementations of the standard
> algorithms using the new iterator traits.
> 
> What do you all think, is this worth while? What your reaction to
> the new iterator_traits class?

I understand your goals, but think that the fix does nothing.  Since
Dave pointed out that there is no required relationship between
iterator_traits reference/pointer and the return type of operators,
they are totally broken anyway.

Let's pretend that they do work.

We have real iterators with value_type, reference, pointer being
T, T&, T* and T& operator*, T* operator->, T& operator[].  Real
iterators are in forward, bidirectional, random_access.  We also
have fictious iterators in input, output.  Output iterators have
value_type void and traits are worthless.  Istream and istreambuf
iterators have value_type T and reference T&; however operator*
returns T const& and T respectively.

Although the standard has been questioned, I have no problem with
the negative real iterators (const_iterator).  Value_type,
reference, pointer as T, T const&, T const* and T const& operator*,
T const* operator->, T const& operator[].

The problem seems to be with iterators which can not return
a reference.  That seems to be orthoginal to the real iterators; so,
let's call them imaginary iterators (value_iterators).  Value_type,
reference, pointer as T, T, ? and T operator*, ? operator->,
T operator[].  Istreambuf solves the operator-> problem by not
having one and having a useless pointer of charT*.  I don't think
that is good enough for the imaginary iterators.  If (*it).m is
valid, it->m should also be valid.

We can also have negative imaginary iterators with T and T const
for those who like unmodifiable rvalues.

I think that the solution is to nail down the return types of the
iterator operators as in the standard tables.  The traits can then
be written to match them.

John