Re: [boost] Interest in flat_iterator for nested containers?

Subject: Re: [boost] Interest in flat_iterator for nested containers?
From: Jeffrey Hellrung (jhellrung_at_[hidden])
Date: 2009-09-27 16:20:38

Christoph Heindl wrote:
> Hi,
> 
> is there any interest in an iterator that provides a flat view of
> nested containers? For example

I've found this pretty useful, and I've coded up and used something like 
this as well (mine's called flat_multirange_iterator).  If interested, I 
can send you the source to give you some ideas, but it makes generous 
use of other (relatively small) reusable components I've developed, so 
it would take a little work to excise it out of my code collection.  It 
allows you to flatten a multirange of arbitrary depth.  I'll elaborate 
below.

> Open questions:
> 
>  * Currently the the value_type passed to boost::iterator_adaptor is
> const qualified based on required reference type of the
> outer_iterator, which renders the code for input iterators unusable,
> right? What's the best way to achieve const correctness?

I derive from iterator_facade, and explicitly provide the reference type 
  (which is the reference type of the deepest-level range) to achieve 
const-correctness.

Well, that's not quite the whole story.  When traversing down the 
hieararchy of ranges, constness is propagated from the outer-most range 
to all inner ranges, which is an imperfect but for-now-workable solution.

>  * The traversal category of flat_iterator is supposed to be the
> 'greatest common divisor' of the inner and outer iterator type. Is
> there a meta-function in boost that provides that type? Currently
> bidirectional traversal is chosen if both, inner and outer iterator,
> are at least of bidirectional traversal. Else forward traversal is
> chosen (which is of course incorrect when incrementable is passed).

I would describe it as the "widest convertible" type, since the 
traversal concepts form a linear hiearchy, but that's not to say your 
description is incorrect ;)  I actually have a facility to get by with 
single-pass traversal by using (the equivalent of) boost::optional's to 
work around the lack of default-constructibility of the underlying 
iterators.  The user can also explicitly provide the traversal type as a 
template parameter.

>  * Stacking flat_iterators to flatten out a hierarchy of arbitrary
> levels is possible but currently requires a lot of typing. I think
> that applying some recursive meta-functions to generate a correct
> iterator types for such situations should be possible but is beyond my
> current knowledge of meta-programming.
> 
> Kind regards,
> Christoph

Right.  I use a boost::fusion::vector of iterator_pack's, where an 
iterator_pack keeps track of the "current position" at the corresponding 
level's iteration:

template< class It, class Traversal >
struct iterator_pack;

template< class It >
struct iterator_pack< It, boost::bidirectional_traversal_tag >
{
     It begin, current, end;
     /* ... */
}

template< class It >
struct iterator_pack< It, boost::forward_traversal_tag >
{
     It current, end;
     /* ... */
}

template<
     class SinglePassReadableMultirange,
     int Dimension,
     class CategoryOrTraversal
 >
struct flat_multirange_iterator
{
     /* ... */
private:
     // Note: multirange_multiiterator evalutes to a Boost.MPL sequence 
of the iterators at each level of the range hierarchy.
     typedef typename boost::fusion::result_of::as_vector<
         typename boost::mpl::transform<
             typename multirange_multiiterator< 
SinglePassReadableMultirange, Dimension >::type,
             detail_iterator::iterator_pack< boost::mpl::_1, 
traversal_type >
         >::type
     >::type iterator_pack_sequence_type;

     iterator_pack_sequence_type m_it_packs;
};

There is also a single-pass traversal version of iterator_pack (which 
holds a boost::optional of a forward-traversal iterator_pack).

I make gratuitous use of the Boost.Fusion transformation algorithms when 
possible, and just straight-up iteration over Boost.Fusion sequences 
otherwise, so (IMHO) the code is not so bad.

Using these iterator_pack's to define the current iteration location 
puts some requirements on the multirange you're flattening, along the 
lines that iterators at deeper levels remain valid even after the 
reference to their parent range goes out of scope.  This has worked fine 
for me so far, but there may be weaker requirements if one uses a 
different strategy...?

I'll take a look at your implementation and see how it compares to what 
I'm currently using.

- Jeff