Subject: Re: [boost] Interest in flat_iterator for nested containers?
From: Christoph Heindl (christoph.heindl_at_[hidden])
Date: 2009-09-28 02:24:10
> 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.
Do you have something better in mind?
>> * 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.
"widest convertible" sounds good to me :)
Do you already have random access traversal support?
>> * 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,
> 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:
Interesting. Didn't throught of such a solution.
> 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.
Keep in mind that it is an early implementation.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk