Boost logo

Boost :

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

> 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

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;
     /* ... */

     class SinglePassReadableMultirange,
     int Dimension,
     class CategoryOrTraversal
struct flat_multirange_iterator
     /* ... */
     // 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 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at