Re: [boost] multimap alternatives. Was: Re: : Review of a safer memory management approach for C++

Subject: Re: [boost] multimap alternatives. Was: Re: : Review of a safer memory management approach for C++
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-06-09 17:48:17

Thorsten Ottosen wrote:
> Simonson, Lucanus J skrev:
> 
>> I never use multimap and prefer map of vectors.
> 
> Hm. Interesting. I assume that your reason is that it
> implies fewer nodes in the multimap
> 
> a) easier balancing/fewer buckets
> b) fewer memory allocations, tighter memory
> c) less memory footprint because the key is only stored once
> 
> Am I right?
> 
> OTOH, iteration is slightly more complicated. I guess this is
> a good example of where segmented iterators could be useful.

There are actually cases where a map of vectors would be less efficient than a multimap when the number of elements with non-unique keys is small, but you are right that there are cases where a map of vectors will be more efficient.

The real reason is more of a defensive programming practice.  Multi-maps are somewhat confusing to work with because the order of insertion for elements with the same key isn't (to my knowledge) well defined.  If you insert an element and it returns an iterator, for example, is that iterator pointing to the first, last or some middle element in a group with the same key value?  It is error prone to work in a mode where your code works for multimaps where elements have unique keys but breaks when multiple elements start sharing a key because it is easy to forget about and no compile time error catches the mistake.  With map of vectors the compiler forces you to handle the case where keys are equal.  With a multimap things become confused when you insert an element and then follow up with a loop that decrements the iterator returned by insert until a condition is met.  With a map of vectors it is much more explicit and self documenting what the code is doing and why.  It also becomes easier to think about the data structure as a map of vectors rather than a flat multimap.  For these reasons I actually would prefer not to use segmented iterators on a map of vectors in most cases since it abstracts away the clarity of the code I'm trying to achieve.

Regards,
Luke