Why does multimap allow duplicate key-value pairs?

EDIT: This answer does not answer the current question anymore. I'll keep it as it is because it got upvoted a lot so it must be useful for some.

The multi in multimap stands for the fact that the same key can occur multiple times.

The standard puts no limit on the type used as value, so one cannot assume that operator==() is defined. Because we don't want the result of your code depend on whether the operator==() is defined or not, it is never used.

std::multimap is not a replacement for std::map. As you noticed, it behaves differently when the same key is inserted multiple times. If you want std::map's behaviour, use std::map.

There is also a std::multiset.

The rational: sometimes one would like to keep all old entries for the same key around as well. [TBD: Insert some example here]

Personally, I barely ever use std::multimap. If I want multiple entries for the same key, I usually rely on std::map<std::vector<T> >.

The values are allowed to be duplicates because they are not required to be comparable to each other. The container cannot do anything with the values besides copy them in. This enables types like multimap< int, my_class >.

If duplicate key-value pairs are undesirable, then use set< pair< T, U > > and use lower_bound to find the first match to a given key.

Multimap only has a predicate ordering the keys. It has no method to determine whether the values are equal. Is value "A" a duplicate of value "a"? Without a second predicate for the values, there's no telling. Therefore, it doesn't even make sense to talk about duplicate values in a multimap.

If you would like a container that stores pairs, and enforces the unique-ness of both parts of the pair, look at boost::multi_index_container. It's very flexible, but takes a load of arguments as a result.