ansaurus

Question

How to write comparator function for qsort?

Answer 1

+4 A:

class classname{
  public:
    int N,M;

    bool operator< (const classname& other) const { return N < other.N; }
};

...
std::vector<classname> arr;
...
std::sort(arr.begin(), arr.end());

Or do you want to use C's qsort?

static int compare_classname (const void* a, const void* b) {
   const classname* _a = reinterpret_cast<const classname*>(a);
   const classname* _b = reinterpret_cast<const classname*>(b);
   return _a->N < _b->N ? -1 : _a->N > _b->N ? 1 : 0;
}
...
classname* arr = new classname[n];
...
qsort(arr, n, sizeof(arr[0]), compare_classname);

KennyTM 2010-01-18 18:35:38

I want to use C's qsort)

SomeUser 2010-01-18 18:37:18

Why? qsort is old and busted. std::sort is the new hotness

Terry Mahaffey 2010-01-18 18:40:38

What's "busted" about `qsort` ?

Charles Bailey 2010-01-18 18:45:08

@Charles: type safety.

Mike Seymour 2010-01-18 18:48:27

@Charles: type safety + speed. Compare the speed of qsort to std::sort

Nemanja Trifunovic 2010-01-18 18:50:55

For most uses of `qsort` type safety isn't usually a concern (it's a simple "bounce" through a `void*`), unless you're accepting random function pointers from code that you don't trust. And yes, std::sort _can_ be faster and also works with non-POD types. But how does any of this make `qsort` "busted" for its intended purpose?

Charles Bailey 2010-01-18 19:00:51

Answer 2

+4 A:

Since you're using C++, my advice would be to use std::sort instead of qsort. In this case, you normally implement your comparison function as operator<:

class classname { 
public:
    int N, M;

    bool operator<(classname const &other) const { 
        return N < other.N;
    }
};

Edit: If you insist on using C's qsort, the comparison function looks something like this:

int comparator(void *a, void *b) { 
     return ((classname *)b)->N - ((classname *)a)->N;
}

Jerry Coffin 2010-01-18 18:36:51

Answer 3

+4 A:

struct Functor {
   bool operator()(const classname & left, const classname & right) {
       return left.N < right.N;
   }
}

std::sort(container.begin(), container.end(), Functor());

Alexey Malistov 2010-01-18 18:36:59

I think technically `operator()` should be `const`. (And you would inherit from `std::binary_function`)

GMan 2010-01-18 23:28:48

Answer 4

+1 A:

In case you really want to you C's qsort (which you shouldn't if you use C++):

int compare(const void * a, const void * b)
{
  return static_cast<classname*>(a)->N < static_cast<classname*>(b)->N;
}

Then just pass compare as the 4th argument of qsort

abenthy 2010-01-18 18:41:05

As it stands, this won't compile. A static_cast needs a type in angle brackets before the value to be cast.

Jerry Coffin 2010-01-18 18:44:33

Thanks. The code was actually right, just my formatting was wrong. I didn't know that <> parts get discarded when one only uses <pre></pre> instead of the 4 spaces.

abenthy 2010-01-18 22:16:47

Answer 5

+2 A:

If you specifically want to use qsort, then the function would be

int compare_classname(const void *a, const void *b)
{
    return static_cast<const classname*>(a)->N 
         - static_cast<const classname*>(b)->N;
}

But as others have said, you're better off with std::sort. It's typesafe, and probably faster since it can inline the comparisons.

Mike Seymour 2010-01-18 18:41:18

Answer 6

+1 A:

This should work.

#include <stdlib.h>


class classname{
public:
    int N,M;
};

static int
cmp_classname(const void * p1, const void * p2) 
{
    const classname * pc1 = reinterpret_cast<const classname *>(p1);
    const classname * pc2 = reinterpret_cast<const classname *>(p2);
    if (pc1->N < pc2->N) {
        return -1;
    } else if (pc1->N > pc2->N) {
        return 1;
    }
    return 0;
}

And, yes, std::sort() is probably better.

Tim Schaeffer 2010-01-18 18:48:21

ansaurus

tags:

views:

answers:

How to write comparator function for qsort?

related questions