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

Subject: Re: [boost] Interest in flat_iterator for nested containers?
From: Christoph Heindl (christoph.heindl_at_[hidden])
Date: 2009-09-28 02:24:10

Jeffrey,

>
> 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.

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,
>> 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:

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...?
>

Again please?

> 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.

Christoph