Comparing struct in c++

Question

Do anyone know a general method to declare a comparision function for struct so that I can use it in sort , priority queue , map ,set ...

I would also know how to specify the comparision function when declaring a data structure (like map ) having a structure as a key (in the case where i have two or more comparision functions)

Thank you in advance

Answer 1

How can the method be "general"?

Let's say you have this struct.

struct MyStruct{
    A a; // A is your own class
};

How would the compiler know how to compare objects of type A?

You need to define a comparison operator yourself.

bool operator()(const MyStruct& s1, const MyStruct& s2);

This function can be given as a compare-function when creating for example a std::map.

explicit map (const key_compare& comp = key_compare(),
          const allocator_type& alloc = allocator_type());

std::map

comp: Binary predicate that, taking two element keys as argument, returns true if the first argument goes before the second argument in the strict weak ordering it defines, and false otherwise.

defaults to

less<key_type>

Answer 2

The comparison function depends from the semantics of your struct. What does it mean that a < b for your type?

In general, a compare function is something along the line of this (references are optional):

bool comp( const YourType& a, const YourType& b );

To make a map use your compare function, you must write like this:

#include <map>

struct YourType{
    int v;
};

struct YourTypeComparison{
    bool operator()( const YourType& a, const YourType& b ) { return a.v < b.v; }
};

int main()
{
    std::map<YourType,int, YourTypeComparison> m;
}

Answer 3

Normally you would use the standard containers like std::map< std::string, int >. But they also have a Comparator type and an Allocator type.

The Comparator used by default is std::less, which looks somewhat like this,

template <class T>
struct less : binary_function <T,T,bool> {
    bool operator() (const T& x, const T& y) const {
        return x<y;
    }
};

(There are some other already made functors http://en.cppreference.com/w/cpp/utility/functional)

Notice that it compares two objects with <. This means that as a "general method" you only need to implement the operator bool operator< (const X& lhs, const X& rhs){...} to allow your objects to be sorted. See Operator Overloading FAQ. As a rule of thumb, if you're going to implement one comparison operator then you should implement the others too.

If you need to sort your keys in another way you can define your own comparator (functor).

template < class T >
struct myLess {
    bool operator()( const T& lhs, const T& rhs ) const {
        return lhs < rhs;
    }
};

And use it in a map like std::map< int, int, myLess<int> >.

You can also not use templates at all if you only need to compare one type.

struct myLess {
    bool operator()( const int& lhs, const int& rhs ) const {
        return lhs < rhs;
    }
};

Then you only have to write std::map< int, int, myLess >.

Keep in mind that the objects you're comparing are the Key types, not necessarily the Contained types.