Hi,
I would like an arbitrarily nested data structure, e.g. similar to
std::vector< std::list<int> >, giving access to the elements of any of
its subcontainers, but, at the same time, being a model of Container -
in particular, having an iterator over all the elements in the last
nesting level (int's in the previous example). Space/time efficiency is
very important in my application.
My solution would be to build a container adaptor similar to
// vector of lists of ... of int
typedef my_nested_container nc_type;
nc_type nc;
(with type lists?) with an iterator adaptor that allows me to write
something like:
for (nc_type::iterator i = nc.begin(); i != nc.end(); ++i)
// do smth with integer *i
The nested container should also allow the user to modify each
subcontainer and to iterate over the elements of a subcontainer,
possibly without (much) overhead, e.g.
// Iteration over the elements of one subcontainer
for (nc_type::inner_iterator j = nc.inner_begin(); j != nc.inner_end();
++j)
// ...
I have started to implement a prototype from scratch, but I am wondering
whether I am reinventing the wheel. I think I can use
boost::iterator_facade for my_nested_container::iterator and/or
boost::pointer_container to build the nested structure internally (to
minimize reallocation overhead upon dynamical change of the structure).
Is there any other boost library I could take advantage from?
I find that operations on a nested container are not completely trivial
to implement (or even to define properly, think of add/remove in
subcontainers which may themselves be nested containers) given its
recursive nature, so I would be very glad to know that something like
that is available off-the-shelf. I have found myself in need for such a
data structure more often than not.
Nicola
