[boost] Interest in flat_iterator for nested containers?

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

Hi,

is there any interest in an iterator that provides a flat view of
nested containers? For example

----------
using namespace boost::assign;

typedef std::list<int> inner_container_type;
typedef std::vector<inner_container_type> outer_container_type;

outer_container_type elements(6);
elements[1] += 1,2,3;
elements[2] += 4,5;
elements[4] += 6;

BOOST_CHECK(std::equal(
   make_flat_iterator(elements.begin(), elements.end()),
   make_flat_iterator(elements.end(), elements.end()),
   list_of(1)(2)(3)(4)(5)(6).begin())
);
----------

If so, I'll be glad to share my code with the boost community. I
attach my current state of development and a single test suite. The
current state of development contains a class named flat_iterator, a
make_flat_iterator function and a set of meta-functions to derive
required types.

flat_iterator derives from boost::iterator_adaptor. It derives an
inner_iterator type from the passed iterator to be adapted
(outer_iterator type). The value_type of outer_iterator is required to
model STL container concept. The value_type passed to
boost::iterator_adaptor is const-qualified if the reference type of
the outer_iterator or inner_iterator type is const-qualified (please
see question 1 below). The traversal category of flat_iterator is
bidirectional if the the outer_iterator and inner_iterator type are at
least bidirectional. It models forward traversal else (question 2).

flat_iterators can be stacked over each other to recursively flatten a
hierarchy of arbitrary levels.

----------
using namespace boost::assign;
typedef std::list<int> level_0;
typedef std::vector<level_0> level_1;
typedef std::vector<level_1> level_2;

level_2 elements(10);
elements[2] += list_of(1)(2);
elements[4] += list_of(3)(4);

typedef flat_iterator<level_2::iterator> flat_iterator_outer;
typedef flat_iterator<flat_iterator_outer> flat_iterator_inner;

flat_iterator_outer outer_begin(elements.begin(), elements.end());
flat_iterator_outer outer_end(elements.end(), elements.end());

flat_iterator_inner inner_begin(outer_begin, outer_end);
flat_iterator_inner inner_end(outer_end, outer_end);

BOOST_CHECK(std::equal(inner_begin, inner_end, list_of(1)(2)(3)(4).begin()));
----------

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?

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

 * 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