[Boost-users] nested containers with boost?

From: nicola (vitacolo_at_[hidden])
Date: 2007-04-04 13:50:59

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<std::vector, std::list, ..., int> 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