qsort比较编译错误。

Question

我的medianfilter.cpp类如下所示调用qsort。

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;
}

我的比较实现如下：

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

而在mediafilter.hpp中声明为私有，并且如下所示：

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

发生编译错误：无法将'type 'int (mediafilter::)(const void*, const void*)'的'mediafilter :: compare'转换为'type '__compar_fn_t {aka int (*)(const void*, const void*)}' 我不完全理解这个错误。如何正确声明和实现此比较方法？ 谢谢！

- feder

---

谢谢大家。即使查看中位数函数也非常友善（实际上它并没有被读取。抱歉，我不应该发布无意义的代码）。 - feder

Answer 1

Compare是一个非静态成员函数，而qsort期望的是非成员函数（或静态成员函数）。由于您的compare函数似乎没有使用类的任何非静态成员，因此可以将其声明为静态。实际上，我不确定您的中位数滤波器类到底是做什么的。也许您只需要一个命名空间。

为什么不直接对向量进行排序，而要将其复制到第二个数组中？此外，如果向量具有超过100个元素，则您的代码将崩溃。

sort的默认行为正是您所需的，但为了完整起见，我展示了如何使用比较函数。

我还更改了您的函数返回类型，因为我不理解为什么一个名为computeMedian的函数不会返回中位数。

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;
        }
    }
}

- Neil Kirk

Answer 2

您不能直接调用compare函数，因为它是一个成员函数，需要一个指向对象的“this”指针才能调用。但是，由于您的compare函数并不需要“this”指针，所以可以将其声明为静态函数，这样您的代码就可以编译了。

在您的类中像这样声明：

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

- The Dark

---

@NeilKirk - 你说得对 - 我从我的测试中复制并粘贴了它，其中我将函数声明在类内部，然后通过手动“修复”来解决。现在应该更好了。 - The Dark

Answer 3

好的，这更像是对Eli Algranti（优秀）答案的附录，而不是对原问题的回答。

这里有一个通用代码来计算名为x的双精度向量的分位数quant（下面的代码保留了它）。

首先要明确的是：分位数有许多定义（仅R就列出了9种）。下面的代码对应于第5个定义（这也是matlab中默认的分位数函数，通常是统计学家想到分位数时所考虑的那个）。

关键思想在于，当分位数不落在精确观测值上时（例如，当您想要长度为10的数组的15%分位数），下面的实现将在相邻分位数之间（在此处为10％和20％之间）实现（正确的）插值。这很重要，这样当您增加观测次数时（我在这里暗示名称medianfilter），分位数的值不会突然跳动，而是平滑地收敛（这是这是统计学家首选定义的一个原因）。

该代码假定x至少有一个元素（下面的代码是较长代码的一部分，我认为这一点已经说过了）。

不幸的是，它使用了许多来自（优秀的！）C++ eigen库的函数，并且在深夜对我来说已经太晚了，无法翻译eigen函数或清理变量名称，但关键思想应该是可读的。

#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);
}

因此，该代码使用了一次nth_element调用，其平均复杂度为O(n)（抱歉我在平均情况下使用了大O符号），并且（当n为偶数时）在向量的最多n/2个元素上额外调用了一次min()函数[在Eigen方言中表示为.minCoeff()]，其复杂度为O(n/2)。

这比使用部分排序（成本为O(nlog(n/2))，最坏情况）或排序（成本为O(nlogn)）要好得多。

- user189035

Answer 4

虽然以下内容与您的问题（您已经得到了答案）没有直接关系，但有些观察：

1. 您计算中位数的方法是错误的。如果元素数量是偶数，则应返回两个中心值的平均值，而不是较小值的值。
2. 将数据复制到一个固定大小的数组中会引发缓冲区溢出的风险。将其复制到另一个向量并使用std:sort进行排序，或者（如@NeilKirk建议的那样）直接对原始数组进行排序，除非您有理由不修改它。
3. 没有针对空输入的防护措施。在这种情况下，中位数未定义，但您的实现只会返回arr [0]上的任意值。

- Eli Algranti

---

此外，您不需要调用sort()来计算中位数，如果元素数量是偶数，则可以通过一次调用nth_element()+一次调用min()来完成。 - user189035

@user189035 很有趣，我在想是否有可能在不排序的情况下计算中位数。 - Neil Kirk

@EliAlgranti：不对，nth_element的时间复杂度是O(n)，而partial sort的时间复杂度是O(nlog(n/2))....点击这里查看详情。 - user189035

@user189035，这是关于std::partial_sort和std::nth_element的实现，它们都是部分排序算法的实例。 - Eli Algranti

@EliAlgranti：不是挑剔，但nth_element是一种选择算法（http://en.wikipedia.org/wiki/Selection_algorithm#Partition-based_selection）。这两者相关但并不相同。 - user189035