Custom Comparators

help
, ,
1

Can anyone guide me how to use custom comparators while sorting vector or in set/map?
I’m a bit confuse about the method’s signatures and parameters(when to use const and pointer), also when to use less than sign(<) and greater than sign(>)?

Thank in advance.

2

I’ll start with qsort. It is a function that can sort any type of data. You have to provide with it:

  1. a base pointer, which points to the start of a contiguous block of data,
  2. the number of elements in the block,
  3. the size of one data member, and
  4. a function that compares two data values.

Since a sorting algorithm in general doesn’t depend upon the type of the data being sorted, qsort() can be written without the knowledge of what data types it is sorting. But to be able to do that, qsort() takes void * parameters, which means “generic pointer” in C. EX:

qsort(data,n, sizeof(int),compare);

Here the sorting of array data which has N integer elements will be done. Compare function will be called for every pair from &data[0] to &data[n-1]. This compare function takes two **const void *** parameters and returns int. While writing this function,ex:

int compare(const void *a, const void *b)
{
   const int* p= (int*)a;
   const int *q= (int*)b;
   // do whatever you want here
  // Usually the convention is, let there are two pointers as arguments to the function. The function     //returns a value less than 0, if The element pointed by p1 goes before the element pointed by p2. 0 if The //element pointed by p1 is equivalent to the element pointed by p2 and >0 if The element pointed by p1 goes after the element pointed by p2

    }

We know that the pointers are passed as int but disguised as void *, thus we need to typecast them. which is done in the first two lines of the function. You may be thinking that why we need to write void * when we know we have integer arguments but think when we have structure nodes. We need the typecast then!!See this:

typedef struct node {
int id;
char foo[255];

} Node;

int compare(const void * x, const void * y) {
    Node * a = (Node *) x;
    Node * b = (Node *) y;
    return a->id - b->id;
}

int main() {
    Node array[SIZE];
    int n;
    ...
    qsort(array, n, sizeof(Node), compare);
    ...
    return 0;
}

Now whenever this qsort is called, compiler doesnot have type information about the comparisons it’ll be making, thus it needs to do that typecast thing everytime. I think you can for now understand that this can make the execution slow, since for every pair it needs to typecase, so extra overhead.

Let’s move on to sort() now,

sort(m.begin(), m.end(),comp)); // m is the map here

comp function: Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool. The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.
The function shall not modify any of its arguments.

bool comp(int i, int j)
{
  return (i<j);
}

Now you may be wondering why we are not using void* here, the reason is that the comparator for sort() accepts references to the actual arguments(which makes it typesafe) while the comparator to qsort does not. Thus, we can simply pass the argument with the actual datatype. The compiler may do the function inline and thus it is fast than the qsort() function.

Also, you can do like:

bool comp(int& a, int &b)  // references
{
  // do here
}

Also, remember that sort uses default comparison operator while qsort does not. As you saw in the example above, return values are decided according to the user’s wish. Also, sort uses iterators while qsort uses pointers.

3

Am I correct, that the function bool comp(int i,int j) mentioned above will be used to sort the element in non-decreasing order…and if we reverse the sign(< to >) it’ll sort in non-increasing order?
Also please tell,how to use custom comparator while inserting values into priority queue,etc.

4

Yes, < will sort in increasing or accurately non-decreasing order and reversing it to > will sort in non-increasing.

5

Can you tell me how to use custom comparator while inserting values into priority queue,etc?

6

I’ll update the answer with the simple code and explanation of that in evening asap. Meanwhile You may refer this: http://stackoverflow.com/questions/16111337/declaring-a-priority-queue-in-c-with-a-custom-comparator.