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-28 03:11:40

Christoph Heindl wrote:
>> 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?

Nope.  I only said "imperfect" because I'm open to there being a more 
correct determination of the reference type.  Like I said, what I have 
now has worked so far.

> Do you already have random access traversal support?

After very little thought when first implementing this, I gave up on 
trying to smartly implement random-access traversal.  For one, you can't 
make constant-time guarantees without additional knowledge of your 
multirange instance (e.g., all subranges are the same size) or 
additional bookkeeping.  Do you have any ideas on how to implement this?

>> 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 assume you want clarification on the general requirements of a 
multirange to be able to present a flattened view of it.  To reiterate, 
I require iterators of a subrange to remain valid even after the 
reference to the parent range has gone out of scope and been destroyed. 
  This usually poses no problems if all reference types are real 
references, but, as a concrete example, you can imagine something like 
the following 2-level multirange:

make_transform_range(outer_range, inner_range_functor())

make_transform_range returns a lazily-evaluated range (basically the 
range-equivalent to a boost::transform_iterator) and inner_range_functor 
is a function object that accepts a value_type of outer_range and 
returns a range itself.  For example

struct inner_range_functor
{
     template< class T >
     boost::array<T,1> operator()(const T& x) const
     {
         boost::array<T,1> result = {{ x }};
         return result;
     }
};

Trying to flatten this using the iterator_pack implementation will fail 
miserably (as I found out the hard way) since the results of applying 
the inner_range_functor to the values of outer_range aren't saved 
anywhere, so iterators into those results are dangling.

Of course, this is a simple example.  Real examples where this causes 
problems are much more opaque, and from the user point-of-view it might 
not be so obvious what expressions should and should not be flattened. 
Like I said, I've been bitten by this problem.

If there was some way to detect the rvalue-ness of the result of 
dereferencing an iterator, and subsequently storing the result in the 
flat_iterator, then the example above might be made to work.  Or 
something else might work.  I don't know :/  I haven't given it too much 
thought since *most of the time*, what I have is sufficient.

- Jeff