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