What's the advantage of multimap over map of vectors?

Question

I don't understand why multimap exists if we can create map of vectors or map of sets. For me only differences are:

using equal_range in multimap for getting elements of a key and in map of vectors we simply use [] operator and have vector of elements.
using multimap.insert(make_pair(key,value)) in multimap for adding elements and map_of_vectors[key].push_back(value) in map of vectors.

So why use multimap? For me it's better to have a vector than two iterators to get all values of a key.

This question applies also to unordered_map of vectors and unordered_multimap.

I must admit I never quite understood the purpose of multimap :/ — Matthieu M.
I little bit late in the question but also multimap consumes much more memory than map of vectors due the extra pointers. The only reason I'd use them is if I want to keep the key of each element (doing push_back you won't keep it) — Jcao02
Multimap is great if you not only want to keep track of duplicate keys of differing values, but you also want to delete any key/value pair at a moments notice. A map of vectors isn't suitable for that, and while you can use a map of lists, it's more convenient to just use a multimap. — richizy
While I see your point (and I also don't tend to use multimap), about the same thing can be said about map<K, V> vs. set<pair<K, V>, cmp_first<K, V>> where cmp_first compares the .first member. — lorro

ypnos ypnos · Accepted Answer · 2010-12-14T10:07:08

I would say it depends on whether all the values with same key have a relationship that you want to address.

So for example, do you often go through all elements with key X, or pass them to a function, and so on? Then it is more convenient to already have them in their separate container, that you can address directly.

However, if you just have a collection of items, that may share same key value, or not, why use vectors in between? It is more convenient to run through the multimap with iterators than have a nested for-loop for the map, vector case.

Another way of looking at this: If multiple entries per key is very common, your structure is more efficient in the map, vector case. If they seldomly happen, it is the opposite.

What's the advantage of multimap over map of vectors?

2 Answers