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.

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

Answer 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 ));
}
 

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

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