iterator adaptors review

From: Martin Weiser (weiser_at_[hidden])
Date: 2000-12-19 06:36:40

General:
========

I've given the iterator adaptors a more or less intense reading. The
overall vote is to accept the iterator adaptors for inclusion in
boost. Detailed comments are listed below.

Besides the reasons mentioned in the library's documentation, I'd like
to see the iterator adaptors in boost for the reason that they are a
promising building block for the View Template Library (VTL) which we
hope to have ready for formal review in a few months.

Code:
=====

The order of template arguments to the iterator_adaptors type
generator should be changed to Iterator, ConstIterator, Policies,
Traits, ConstTraits. What makes the iterator adaptors interesting is
using a nontrivial (nondefault) policy. Thus, in general I will
provide a nondefault policy. With the current ordering I will have to
specify the iterator traits as well, even if the default template
parameters are perfectly sensible. Furthermore, the change would match
the iterator_adaptor implementation template.

template <class Iterator, class ConstIterator,
          class Traits = std::iterator_traits<Iterator>,
          class ConstTraits = std::iterator_traits<ConstIterator>,
          class Policies = default_iterator_policies> >
class iterator_adaptors ...

As already suggested by Beman, iterator_adaptors<> and
iterator_adaptor<> should be named more differently. Perhaps the
iterator_adaptor implementation template could be moved to a details::
namespace, leaving the type generator as interface to the library.

Then what do we do with situations where there is only one kind of
iteratos? This could be handled by specifying a default for mutable
iterators that is just the immutable iterator (similar to set). The
template parameter list for the type generator would then be

template <class Policies,
          class ConstIterator,
          class Iterator = ConstIterator,
          class ConstTraits = std::iterator_traits<ConstIterator>,
          class Traits = std::iterator_traits<Iterator> >

Maybe this is a too far reaching change or not at all a good idea.

For the transform iterator, the requirement of the transformation to
be an adaptable unary function could possibly relaxed using a function
traits class deducing the return type for function pointers. I
remember such a traits class was mentioned on the list, but is it
available in boost? Other reasons against? Partial specialization? If
so, this design rationale should be documented.

I think the reverse iterator could be removed from the code and be
used solely in the documentation as illustrating example. This would
eliminate possible confusion with the standard reverse iterator
adaptor.

The difference between transform and projection iterators is 
essentially, as explained in the documentation, the generation
vs. existence of the result. Does someone have an idea for more
concise names reflecting the difference better?

If the VTL should be included into boost in a few months, the integer
range container should be moved to the VTL.

Documentation:
==============

AFAIK iterators need to be default constructible, and in fact the
iterator_adaptor provides a default constructor. This should be
reflected in the documentation (end of section "Iterator Adaptors
Class"). I guess the policies classes need to be default
constructible, too, and the requirement seems to be implicit in the
iterator adaptor constructors given, but should be made explicit.

I failed to relate the "Implementation Notes" section to the
code. There do not seem to be forward_iterator_adaptor etc. 
Either the documentation or the code seems to be outdated.

Future directions:
==================

I'd like to see two extensions in future versions of the library.

First, there are quite a few interesting things you can do using
*two* iterators to adapt instead of one. The extension to double
iterator adaptors is therefore a promising direction to take.

Second, there are some situations where transform iterators could 
be mutable. It's a highly nontrivial task and will probably need
the definition of a semi-invertible adaptable unary function concept,
but it could be quite rewarding.

Yours,
Martin