Why does multimap allow duplicate key-value pairs?

Question

EDIT: Please note, I'm NOT asking why multimap can't contain duplicate keys.

What's the rationale behind multimap allowing duplicate key-value pairs? (not keys)

#include <map>
#include <string>
#include <iostream>

int
main(int argc, char** argv)
{
    std::multimap<std::string, std::string> m;
    m.insert(std::make_pair("A", "B"));
    m.insert(std::make_pair("A", "B"));
    m.insert(std::make_pair("A", "C"));
    std::cout << m.size() << std::endl;
    return 0;
}

This printed 3, which somewhat surprised me, I expected multimap to behave like a set of pairs, so I was expecting 2.

Intuitively, it's not consistent with C++ std::map behaviour, where insert does not always change the map (as opposed to operator[]).

Is there a rationale behind it, or it's just arbitrary?

Answer 1

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.

Answer 2

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> >.