Boost logo

Boost :

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

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