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.

score 75 · Accepted Answer · answered Jul 04 '11 at 15:17

75

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

answered Jul 04 '11 at 15:17

James Kanze

150,581
18
184
329

+1 Indeed, it is copyable and assignable that are the real requirements. – juanchopanza Jul 04 '11 at 15:21
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? – nurdglaw Aug 09 '18 at 15:53
5

@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_an_ai Aug 20 '18 at 17:46
@nurdglaw anyhow, it could be that the "preferably as function object" refers to the other alternatives: (named) member method or free function – 463035818_is_not_an_ai Aug 20 '18 at 17:50
1

I read it as <> 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. – Gem Taylor Aug 20 '18 at 18:31
@user463035818 Thanks for the response. I guess I was thinking of using keys with a natural ordering function so wasn't looking past `operator <` – nurdglaw Aug 23 '18 at 13:32

score 27 · Answer 2 · edited Oct 20 '21 at 20:52

27

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

edited Oct 20 '21 at 20:52

Milan Babuškov

59,775
49
126
179

answered Jul 04 '11 at 15:14

BЈовић

62,405
41
173
273

2

That's a terrible comparison operator. – Kerrek SB Jul 04 '11 at 15:17
1

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") – Martin York Jul 04 '11 at 15:38
Right, I wanted to post a simple example and got to screw it up. Thanks Martin for fixing the example. – BЈовић Jul 04 '11 at 19:14

score 4 · Answer 3 · answered Jul 04 '11 at 15:14

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

score 2 · Answer 4 · answered Jul 04 '11 at 15:12

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.

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

4 Answers4

Linked

Related