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.

Answer 1

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.