What is the usage of std::multimap?

Question

I've just started learning STL containers, and I cannot understand why std::multimap exists. With std::map, we can access values by user-defined keys, but with std::multimap we cannot do that as the latter does not even have an overloaded operator[] and the same key can be mapped to several different values. To me, this looks like std::multimap is essentialy just something like std::multiset<std::pair<K, V>> with the Compare function operating on the K and we lose the main feature of a map which is the ability to access elements by key (as I see it). I've found this post, but still couldn't comprehend the usecases given here. Could someone please give me several examples when we would use std::multimap?

Answer 1

First note that std::map::operator[] is a little quirky. It is not the way to access elements in the map. Instead std::map::operator[] potentially inserts an element into the map and then returns a reference to either the element that was already present before or to the newly inserted. This may seem like splitting hairs, but the difference matters. The way to access a mapped_value given a key in a std::map is std::map::find. std::multimap has a find as well. No big difference with respect to that.

std::map::at has not counterpart in std::multimap because std::map::at returns a reference to the mapped_value for the given key, but in the multimap there can be more than one mapped_value for the same key, so it isnt obvious what a std::multimap::at should return if it existed. Finding and accessing elements can be done with find for both maps.

A std::multimap<K,V> can be compared to a std::map<K,std::vector<V>> but with the interface you'd expect when you want to map more than a single value to the same key. For example std::multimap iterators lets you iterate all key-value pairs in the multimap in one go. With the map of vectors you'd have to use the maps iterators and the vectors iterators. Using the map of vectors with standard algorithms is rather cumbersome. Further, std::multimap::count returns the number of elements for a given key. With the map of vectors you would have to first find the vector for given key and call its size. This list is not complete, but I hope the difference gets clear.

One example for a multimap could be inhabitants of houses. In the same house lives more than one person. If you want to map street number to person you could use a multimap.

More generally, if you have a collection / container of elements and you want to divide them into distinct groups, you can use a multimap. A common use of std::map (or std::unordered_map) is to count frequencies, eg:

  std::map<int,int> freq;
  for (const auto& x : some_container) {
       ++freq[ x % 3 ];
  }

This counts how many elements of some_container are divisible by 3, without remainder, with remainder 1, or with remainder 2. If you want to know the elements rather than only count them you can use a std::multimap.