16

I have a class with a few numeric fields such as:

class Class1 {
    int a;
    int b;
    int c;
public:
    // constructor and so on...
    bool operator<(const Class1& other) const;
};

I need to use objects of this class as a key in an std::map. I therefore implement operator<. What is the simplest implementation of operator< to use here?

EDIT: The meaning of < can be assumed so as to guarantee uniqueness as long as any of the fields are unequal.

EDIT 2:

A simplistic implementation:

bool Class1::operator<(const Class1& other) const {
    if(a < other.a) return true;
    if(a > other.a) return false;

    if(b < other.b) return true;
    if(b > other.b) return false;

    if(c < other.c) return true;
    if(c > other.c) return false;

    return false;
}

The whole reason behind this post is just that I found the above implementation too verbose. There ought to be something simpler.

1
  • You must first decide what '<' means for the case where multiple members represent the invariant of the class. Jun 9, 2010 at 13:52

5 Answers 5

40

I assume you want to implement lexicographical ordering.

Prior to C++11:

#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_comparison.hpp>
bool Class1::operator<(const Class1& other) const
{
    return boost::tie(a, b, c) < boost::tie(other.a, other.b, other.c);
}

Since C++11:

#include <tuple>
bool Class1::operator<(const Class1& other) const
{
    return std::tie(a, b, c) < std::tie(other.a, other.b, other.c);
}
4
  • Nice! But boost is too heavy for my particular case. Jun 9, 2010 at 14:01
  • Great, never thought of using tuples! Jun 9, 2010 at 14:27
  • 1
    @Agnel Kurian: no need to 'use' it further than this one tie. It is header-only too, to minimize build impact (time/dependencies) you can isolate it into a separate compilation unit (but for release builds, consider doing it in the header for inlining!)
    – sehe
    May 24, 2011 at 20:50
  • 5
    With a recent compiler you can use std::tie after including <tuple> header :)
    – fmuecke
    May 9, 2014 at 20:56
15

I think there is a misunderstanding on what map requires.

map does not require your class to have operator< defined. It requires a suitable comparison predicate to be passed, which conveniently defaults to std::less<Key> which uses operator< on the Key.

You should not implement operator< to fit your key in the map. You should implement it only if you to define it for this class: ie if it's meaningful.

You could perfectly define a predicate:

struct Compare: std::binary_function<Key,Key,bool>
{
  bool operator()(const Key& lhs, const Key& rhs) const { ... }
};

And then:

typedef std::map<Key,Value,Compare> my_map_t;
7

It depends on if the ordering is important to you in any way. If not, you could just do this:

bool operator<(const Class1& other) const
{
    if(a == other.a)
    {
         if(b == other.b)
         {
             return c < other.c;
         }
         else
         {
             return b < other.b;
         }
    }
    else
    {
        return a < other.a;
    }
}
2
  • Or, for fun, return a!=other.a?a<other.a:b!=other.b?b<other.b:c<other.c;
    – Skizz
    Jun 9, 2010 at 14:15
  • 10
    I don't see in what way this is better than the "simplistic implementation" that the OP gave. This version is less readable.
    – Frank
    Jun 26, 2012 at 20:43
0

A version which avoids multiple indentation is

bool operator<(const Class1& other) const
{
    if(a != other.a)
    {
        return a < other.a;
    }

    if(b != other.b)
    {
        return b < other.b;
    }

    return c < other.c;
}

The "Edit 2" version of the author has on average more comparisons than this solution. (worst case 6 to worst case 3)

-4

You could do:

return memcmp (this, &other, sizeof *this) < 0;

but that has quite a lot of of caveats - no vtbl for example and plenty more I'm sure.

1
  • @Peter: The OP only wants to guarantee uniqueness as long as any of the fields are unequal, so, adding an offsetof to get the address of the first key field and ensuring the key fields are contiguous, memcmp should do the trick.
    – Skizz
    Jun 9, 2010 at 14:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.