qsort comparison compilation error

Question

My medianfilter.cpp class invokes qsort as seen below.

vector<float> medianfilter::computeMedian(vector<float> v) {
    float arr[100];
    std::copy(v.begin(), v.end(), arr);

    unsigned int i;
    qsort(arr, v.size(), sizeof(float), compare);
    for (i = 0; i < v.size(); i++) {
        printf("%f ", arr[i]);
    }
    printf("median=%d ", arr[v.size() / 2]);
    return v;
}

The implementaiton of my comparison is:

int medianfilter::compare(const void * a, const void * b) {
    float fa = *(const float*) a;
    float fb = *(const float*) b;
    return (fa > fb) - (fa < fb);
}

while the declaration in mediafilter.hpp is set private and looks like that:

int compare (const void*, const void*);

A compilation error occurs: cannot convert ‘mediafilter::compare’ from type ‘int (mediafilter::)(const void*, const void*)’ to type ‘__compar_fn_t {aka int (*)(const void*, const void*)}’

I don't understand this error completly. How do I correctly declare and implement this comparison method? Thanks!

Answer 1

Ok, this is more of an appendix to Eli Algranti (excellent) answer than an answer to the original question.

Here is a generic code to compute the quantile quant of a vector of double called x (which the code below preserves).

First things first: there are many definitions of quantiles (R alone lists 9). The code below corresponds to definition #5 (which is also the default quantile function in matlab and generally the ones statisticians think of when they think quantile).

The key idea here is that when the quantile do not fall on a precise observation (e.g. when you want the 15% quantile of an array of length 10) the implementation below realizes the (correct) interpolation (in this case between the 10% and 20%) between adjacent quantile. This is important so that when you increase the number of observations (i m hinting at the name medianfilter here) the value of the quantile do not jump about abruptly but converges smoothly instead (which is one reason why this is the statistician's preferred definition).

The code assumes that x has at least one element (the code below is part of a longer one and I feel this point has been made already).

Unfortunately it s written using many function from the (excellent!) c++ eigen library and it is too late for me at this advanced time in the night to translate the eigen functions --or sanitize the variable names--, but the key ideas should be readable.

#include <Eigen/Dense>
#include <Eigen/QR>

using namespace std;
using namespace Eigen;
using Eigen::MatrixXd;
using Eigen::VectorXd;
using Eigen::VectorXi;

double quantiles(const Ref<const VectorXd>& x,const double quant){
//computes the quantile 'quant' of x.
    const int n=x.size();
    double lq,uq,fq;
    const double q1=n*(double)quant+0.5;
    const int index1=floor(q1);
    const int index2=ceil(q1);
    const double index3=(double)index2-q1;
    VectorXd x1=x;
    std::nth_element(x1.data(),x1.data()+index1-1,x1.data()+x1.size());
    lq=x1(index1-1);
    if(index1==index2){
        fq=lq;
    } else {
        uq=x1.segment(index1,x1.size()-index1-1).minCoeff();
        fq=lq*index3+uq*(1.0-index3);
    }
    return(fq);
}

So the code uses one call to nth_element, which has average complexity O(n) [sorry for sloppely using big O for average] and (when n is even) one extra call to min() [which in eigen dialect is noted .minCoeff()] on at most n/2 elements of the vector, which is O(n/2).

This is much better than using partial sort (which would cost O(nlog(n/2)), worst case) or sort (which would cost O(nlogn))

Answer 2

Compare is a non-static member function whereas qsort expects a non-member function (or a static member function). As your compare function doesn't seem to use any non-static members of the class, you could just declare it static. In fact I'm not sure what your median filter class does at all. Perhaps you just need a namespace.

Why not sort the vector directly instead of copying it into a second array? Furthermore your code will break if the vector has more than 100 elements.

The default behavior of sort does just want you need, but for completeness I show how to use a compare function.

I also changed the return type of your function because I don't understand why a function called computeMedian wouldn't return the median..

namespace medianfilter
{
    bool compare(float fa, float fb)
    {
        return fa < fb;
    }

    float computeMedian(vector<float> v)
    {
        std::sort(v.begin(), v.end(), compare);
        // or simply: std::sort(v.begin(), v.end());
        for (size_t i = 0; i < v.size(); i++) {
            printf("%f ", v[i]);
        }

        if (v.empty())
        {
            // what do you want to happen here?
        }
        else
        {
            float median = v[v.size() / 2]; // what should happen if size is odd?
            printf("median=%f ", median); // it was %d before
            return median;
        }
    }
}

Answer 3

Not directly related to your question (for which you already have the answer) but some observations:

1. Your calculation of median is wrong. If the number of elements is even you should return the average of the two center values not the value of lower one.
2. The copy to the array with a set size screams buffer overflow. Copy to another vector and std:sort it or (as suggested by @NeilKirk) just sort the original one unless you have cause not to modify it.
3. There is no guard against empty input. Median is undefined in this case but your implementation would just return whatever happens to be on arr[0]

Answer 4

You can't call compare as it is because it is a member function and requires a this pointer (i.e. it needs to be called on an object). However, as your compare function doesn't need a this pointer, simply make it a static function and your code will compile.

Declare it like this in your class:

static int compare(const void * a, const void * b);