What requirements must std::map key classes meet to be valid keys?

Question

I want to map objects of a given class to objects of another. The class I want to use as key, however, was not written by me and is a simple struct with a few values. std::map orders it's contents, and I was wondering how it does it, and if any arbitrary class can be used as a key or if there's a set of requirements (operators and what not) that need to be defined.

If so, I could create a wrapper for the class implementing the operators map uses. I just need to know what I need to implement first, and none of the references for the class I found online specify them.

Solution 1

All that is required of the key is that it be copiable and assignable. The ordering within the map is defined by the third argument to the template (and the argument to the constructor, if used). This defaults to std::less<KeyType>, which defaults to the < operator, but there's no requirement to use the defaults. Just write a comparison operator (preferably as a functional object):

struct CmpMyType
{
    bool operator()( MyType const& lhs, MyType const& rhs ) const
    {
        //  ...
    }
};

Note that it must define a strict ordering, i.e. if CmpMyType()( a, b ) returns true, then CmpMyType()( b, a ) must return false, and if both return false, the elements are considered equal (members of the same equivalence class).

Solution 2

You need to define the operator<, for example like this :

struct A
{
  int a;
  std::string b;
};

// Simple but wrong as it does not provide the strict weak ordering.    
// As A(5,"a") and A(5,"b") would be considered equal using this function.
bool operator<(const A& l, const A& r )
{
  return ( l.a < r.a ) && ( l.b < r.b );
}

// Better brute force.
bool operator<(const A& l, const A& r )
{ 
    if ( l.a < r.a )  return true;
    if ( l.a > r.a )  return false;

    // a are equal, compare b
    return ( l.b < r.b );
}

// This can often be seen written as
bool operator<(const A& l, const A& r )
{
   // This is fine for a small number of members.
   // But I prefer the brute force approach when you start to get lots of members.
   return ( l.a < r.a ) ||
          (( l.a == r.a) && ( l.b < r.b ));
}
 

Solution 3

The answer is actually in the reference you link, under the description of the "Compare" template argument.

The only requirement is that Compare (which defaults to less<Key>, which defaults to using operator< to compare keys) must be a "strict weak ordering".

Solution 4

Same as for set: The class must have a strict ordering in the spirit of "less than". Either overload an appropriate operator<, or provide a custom predicate. Any two objects a and b for which !(a<b) && !(b>a) will be considered equal.

The map container will actually keep all the elements in the order provided by that ordering, which is how you can achieve O(log n) lookup and insertion time by key value.

View more solutions

Comments

[Kerrek SB]

That's a terrible comparison operator.

[juanchopanza]

+1 Indeed, it is copyable and assignable that are the real requirements.

[Martin York]

It was not only terrible it was wrong. It did not provide the "strict weak ordering" required by the map container. Have provided a brute force version above to compensate. Compare the difference between A(5,"A") and A(5,"B")

[BЈовић]

Right, I wanted to post a simple example and got to screw it up. Thanks Martin for fixing the example.

[nurdglaw]

Why "preferably as a function object". Why not as operator < on the candidate class? Admittedly, the OP doesn't control the class so can't add an operator, but in my case it is possible. Is it undesirable to add a comparison operator, and if so, why?

[463035818_is_not_a_number]

@nurdglaw I saw a talk recently where one of the gurus was ranting about providing an operator< for each and every class. He gave the example of chairs. You could sort them by height, number of legs or even by color, but whatever you choose is completely arbitrary and in fact there is no natural ordering for chairs, but it is rather the container that has to choose in what way the chairs should be ordered. Too often a operator< that seems an obvious choice is really just one out of many possibilities and as such does not belong into the class....something along this line was his reasoning.

[463035818_is_not_a_number]

@nurdglaw anyhow, it could be that the "preferably as function object" refers to the other alternatives: (named) member method or free function

[Gem Taylor]

I read it as <<If operator < and std::less don't do it for you, then write a comparator function as an extra argument to the std::map template declaration. If you do the comparator function it is best to declare it as a functor object>> The reason it is better to do the functor object is that the object instance is optimised away at compile time, while the function pointer physically exists in the map object and is much harder to optimise away.

[nurdglaw]

@user463035818 Thanks for the response. I guess I was thinking of using keys with a natural ordering function so wasn't looking past operator <