Is this use of nested vector/multimap/map okay?

Question

I am looking for the perfect data structure for the following scenario:

I have an index i, and for each one I need to support the following operation 1: Quickly look up its Foo objects (see below), each of which is associated with a double value.

So I did this:

struct Foo {
  int a, b, c;
};

typedef std::map<Foo, double> VecElem;
std::vector<VecElem> vec;

But it turns out to be inefficient because I also have to provide very fast support for the following operation 2: Remove all Foos that have a certain value for a and b (together with the associated double values).

To perform this operation 2, I have to iterate over the maps in the vector, checking the Foos for their a and b values and erasing them one by one from the map, which seems to be very expensive.

So I am now considering this data structure instead:

struct Foo0 {
  int a, b;
};

typedef std::multimap<Foo0, std::map<int, double> > VecElem;
std::vector<VecElem> vec;

This should provide fast support for both operations 1 and 2 above. Is that reasonable? Is there lots of overhead from the nested container structures?

Note: Each of the multimaps will usually only have one or two keys (of type Foo0), each of which will have about 5-20 values (of type std::map<int,double>).

Answer 1

To answer the headline question: yes, nesting STL containers is perfectly fine. Depending on your usage profile, this could result in excessive copying behind the scenes though. A better option might be to wrap the contents of all but top-level container using Boost::shared_ptr, so that container housekeeping does not require a deep copy of your nested container's entire contents. This would be the case say if you plan on spending a lot of time inserting and removing VecElem in the toplevel vector - expensive if VecElem is a direct multimap.

Memory overhead in the data structures is likely to be not significantly worse than anything you could design with equivalent functionality, and more likely better unless you plan to spend more time on this than is healthy.

Answer 2

Well, you have a reasonable start on this idea ... but there are some questions that must be addressed first.

For instance, is the type Foo mutable? If it is, then you need to be careful about creating a type Foo0 (um ... a different name may be a good idea hear to avoid confusion) since changes to Foo may invalidate Foo0.

Second, you need to decide whether you also need this structure to work well for inserts/updates. If the population of Foo is static and unchanging - this isn't an issue, but if it isn't, you may end up spending a lot of time maintaining Vec and VecElem.

As far as the question of nesting STL containers goes, this is fine - and is often used to create arbitrarily complex structures.