Sign in to follow this  
GenuineXP

std::multimapK, V vs std::mapK, std::vectorV

Recommended Posts

GenuineXP    262
So I'm wondering what the differences/advantages/disadvantages are of using a std::multimap<K, V> as opposed to a std::map<K, std::vector<V> > container. The former is simpler in that it's a single container, but the latter makes it easier to traverse elements with a given key or to "export" those elements to other objects or algorithms as a std::vector. On the other hand, std::multimap will never invalidate iterators after an insertion or deletion and the std::vector most certainly would. I ask because I'm trying to isolate groups of objects with different keys and will need to be able to iterate over them as well as expose a list of objects from each group. Using a std::multimap, I would have to give clients iterators for the objects of interest, or stuff them into another container (e.g. a std::vector) whenever clients needed it (and this happens very, very frequently). With the std::map approach, I need only to return the underlying std::vector and I'm done. In a sense, a std::map<K, std::vector<V> > emulates a std::multimap, with the exception of iterator invalidation and applying certain algorithms. Actually, I can see how it would be easier to apply algorithms to an underlying std::vector than to a std::multimap since it requires binding members to accommodate std::pair<K, V> objects! Discuss? :-)

Share this post


Link to post
Share on other sites
frob    44913
>> I ask because I'm trying to isolate groups of objects with different keys and will need to be able to iterate over them as well as expose a list of objects from each group.

You don't need a single container that does all this.

Consider this situtation:

Use your map to have key/*object pairs.
Use another container (probably a multimap) to handle group/*object pairs
If you need to group in yet another way, create another container and use searches, filters or sorts as needed using functions from <algorithms>

Share this post


Link to post
Share on other sites
jpetrie    13106
Quote:

The former is simpler in that it's a single container, but the latter makes it easier to traverse elements with a given key or to "export" those elements to other objects or algorithms as a std::vector. On the other hand, std::multimap will never invalidate iterators after an insertion or deletion and the std::vector most certainly would.

Can you elaborate on this? To iterate the values for a key in the map-of-vector, you do:

map< KEY,vector<VALUE> >::iterator it = container.find(key);
vector<VALUE>::iterator vit = it->second.begin();
while( vit != it->second.end() )
{
// Whatever.
++vit;
}

and with a multimap, you do

multimap< KEY, VALUE >::iterator it = container.find(key);
while( it != container.upper_bound(key) )
{
// Whatever.
++it;
}

which are essentially the same. Are you speaking of the issue that the iterators in the multimap case are of pairs and not values alone?

Share this post


Link to post
Share on other sites
GenuineXP    262
What I meant by being easier to traverse or export is like the following.

typedef std::map<K, std::vector<V> > con_t;
class some_class {
public:
const std::vector<V>& group(const K& key) const;
void do_stuff();
private:
void process(const V& value);
con_t _con;
};
const std::vector<V>& some_class::group(const K& key) const {
con_t::iterator i;
if ((i = _con.find(key)) == _con.end()) { throw std::runtime_error("uh oh"); }
return i->second;
}
void some_class::do_stuff() {
// Process group "0".
con_t::iterator i;
if ((i = _con.find(0)) == _con.end()) { return; }
std::vector<V>& group = i->second;
// Binding is a bit simpler, since this is just a plain ol' vector.
std::for_each(group.begin(), group.end(), boost::bind(&some_class::process, this, _1));
}


Forgive any errors; I typed this up directly in this reply. :-)

Anyway, some_class::group() simply returns the underlying std::vector to clients; there's no need to reformat, repack, or create a new container from scratch. (Of course, returning a reference means this function has to throw if it's not found.)

The some_class::do_stuff() function isn't much simpler than if this example had used a std::multimap, but you can still see how easy it is to apply algorithms to different groups. Not only that, but groups can be passed around within the some_class class for processing as std::vector references rather than pairs of iterators to std::pair<K, V> objects, which are more annoying to work with.

I bring up the idea of a multimap vs a map because (as seen in a previous post of mine) I'm using an interface object in my game engine to store events scanned from a runtime module (plugin). In doing this, I'm storing a map of vectors of events that have occurred during a cycle, where the key is the event type. I thought this may be easier to work with in the end rather than a multimap which would require exposing iterators to pair<K, V> object to clients... yuck. :-)

I'm just curious if this is wise, if there is a performance difference, and I'm wondering if there are any interesting details or side effects of using a map vs a multimap in this way.

Thanks for the replies!

Share this post


Link to post
Share on other sites
frob    44913
Quote:
Original post by GenuineXP
I'm just curious if this is wise, if there is a performance difference

The performance difference is trivial in most situations. Generally you shouldn't worry about it unless you have a half million or so objects in there, or are on a computer where the processor is measured in MHz rather than GHz, or are on a team where the application is actually profiled for performance reasons.

The container classes are quite fast, and are (almost) never a bottleneck. The only exception is when you are misusing them, such as copying vectors from one to another by inserting and deleting one record at a time.

Share this post


Link to post
Share on other sites
osmanb    2082
I haven't fully thought this out, but couldn't you make an iterator adaptor for the multimap iterators that behaves as though it's just iterating over the value half of the stored pairs? At which point the client code can just be templated over iterator-of-value, which can be obtained using either storage mechanism? Seems like you'd end up with the best of both worlds...

Share this post


Link to post
Share on other sites
frob    44913
Quote:
Original post by osmanb
I haven't fully thought this out, but couldn't you make an iterator adaptor for the multimap iterators that behaves as though it's just iterating over the value half of the stored pairs? At which point the client code can just be templated over iterator-of-value, which can be obtained using either storage mechanism? Seems like you'd end up with the best of both worlds...


That is basically what I said above. One of the functions in the algorithms library is stl::find(). Provide a predicate for the thing you are searching for, and all of this is done automatically for you.

There are other algorithms for the other things you mentioned. If you don't know what those are, you should learn about them by working throuh a good book. One well written and thorough book like "The C++ Standard Library" by Nicolai Josuttis.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this