Requirement for key in std::multimap

Question

I have a std::multimap where key is a custom class. Something like this:

Class X {
public:
    std::string s;
    int x;
    operator <(const X& other) const { return s < other.s; }
};
std::multimap<X, int> mymap;

Now, I'd like to use upper_bound and lower_bound to iterate over all elements with the same value of "s". Do I need to implement some other operator for X (for example: ==). Or it will work properly just like this?

Also, what should I supply as argument for *upper_bound* and *lower_bound*? I assume I should create a dummy object with desired value of "s"?

Answer 1

you only need to provide an operator == and <.

upper_bound and lower_bound are just like any other find-type method, so you need the same kind of object to compare with - in your case, a 'dummy' object with the required value of s.

edit: the comments are correct that you only need operator< for lower/upper_bound, and find. But if you want to call other methods on your container, you will need operator== as well. Eg. if you want to sort() your container, you will need operator==.

The 2 overloads you need for all STL containers are operator< and operator==. I find its best practise to implement them both.

Of course, the question could also be answered more fully by implementing a comparison functor in the map itself, not relying on the objects. This is often a good way to implement different ways of calling find() on the map.

Answer 2

Since class X is the key for the multimap, the parameter to upper_bound()/lower_bound() needs to be of that type. If class X has an implicit conversion from std::string (which is the type of X::s) then you can use that as the parameter to upper_bound()/lower_bound().

The default comparison for multimap is less<> which simply calls operator <() - so that's the only operator you a required to have in class X for the multimap to work.