Use cases of std::multimap

Question

I don't quite get the purpose of this data structure. What's the difference between std::multimap<K, V> and std::map<K, std::vector<V>>. The same goes for std::multiset- it could just be std::map<K, int> where the int counts the number of occurrences of K. Am I missing something on the uses of these structures?

Satanism

Answer 1

A counter-example seems to be in order.

Consider a PhoneEntry in an AdressList grouped by name.

int AdressListCompare(const PhoneEntry& p1, const PhoneEntry& p2){
    return p1.name<p2.name;
}

multiset<PhoneEntry, AdressListCompare> adressList;

adressList.insert( PhoneEntry("Cpt.G", "123-456", "Cellular") );    
adressList.insert( PhoneEntry("Cpt.G", "234-567", "Work") );
// Getting the entries
addressList.equal_range( PhoneENtry("Cpt.G") ); // All numbers

This would not be feasible with a set+count. Your Object+count approach seems to be faster if this behavior is not required. For instance the multiset::count() member states

"Complexity: logarithmic in size + linear in count."

Regimentals

+1 Good example of using custom predicates to put STL containers to good use. – Algebraic

This would seem to be quite identical to map<std::string, std::vector<rest of PhoneEntry>>. Whilst admittedly not identical to my proposed replacement, it can also be de-composed. – Satanism

@DeadMG True, but as Alan points out, the iterators behaves very differently for a multiset than the vector combo. Also AdressListCompare doesn't necessarily need to compare only one member. – Regimentals

If it were stored as a map<K, vector<V>> you'd only have that data stored once. In your example, the multiset stores the key repeatedly, because it's part of the value. – Satanism

@DeadMG Good point. I think we have managed to show the important distinctions between the two approaches; at the very least, that it is useful to consider both approaches when dealing with a dataset like this. – Regimentals

Answer 2

You could use make the substitutions that you suggest, and extract similar behavior. But the interfaces would be very different than when dealing with regular standard containers. A major design theme of these containers is that they share as much interface as possible, making them as interchangeable as possible so that the appropriate container can be chosen without having to change the code that uses it.

For instance, std::map<K, std::vector<V>> would have iterators that dereference to std::pair<K, std::vector<V>> instead of std::pair<K, V>. std::map<K, std::vector<V>>::Count() wouldn't return the correct result, failing to account for the duplicates in the vector. Of course you could change your code to do the extra steps needed to correct for this, but now you are interfacing with the container in a much different way. You can't later drop in unordered_map or some other map implementation to see it performs better.

In a broader sense, you are breaking the container abstraction by handling container implementation details in your code rather than having a container that handles it's own business.

It's entirely possible that your compiler's implementation of std::multimap is really just a wrapper around std::map<K, std::vector<V>>. Or it might not be. It could be more efficient and friendly to object pool allocation (which vectors are not).

Using std::map<K, int> instead of std::multiset is the same case. Count() would not return the expected value, iterators will not iterate over the duplicates, iterators will dereference to std::pair<k, int> instead of directly to `K.

Poff

Answer 3

A multimap or multiset allows you to have elements with duplicate keys.

ie a set is a non-ordered group of elements that are all unique in that {A,B,C} == {B,C,A}

Elonore

This completely doesn't answer the question. – Satanism