与 stl sort() 的比较

Question

我正在尝试在类函数中使用 stl sort() 。我想对如下所示的结构数组进行排序：

struct foo{
    double num;
    std::string s;
};

使用如下比较函数：

bool aGreaterThanb(foo a, foo b){
    if (a.num > b.num){
        if(a.num == b.num){
            if (anotherOutsideComparison(a.s, b.s)){
                return true;
            }
        }
        else
            return true;
    }
    else
        return false;
}

但我不确定如何格式化它以使其进行编译。我应该如何格式化它以便我可以调用 sort(fooarray[0], fooarray[end], aGreaterThanb);？ （举个例子就太好了）

Answer 1

将比较函数编写为称为函子的结构的 operator() 方法：

struct aGreaterThanb
{
    bool operator() (const foo& a, const foo& b)
    {
        // return true iff a is strictly less than b according to your ordering
    }
};

然后将该函子对象的实例传递给 std::sort：

std::sort(fooarray.begin(), fooarray.end(), aGreaterThanb());

Answer 2

如果您使用像这样的 foo 数组：

foo fooarray[Foos];
...
sort(fooarray, fooarray + Foos, &aGreaterThanb);

上面的代码将以相反的顺序对数组进行排序，因为 sort 需要一个小于比较器。

此外，为了避免为了比较而复制大量 foo 对象，请声明您的比较器以 const foo& 而不是 foo 作为参数。

bool aGreaterThanb(const foo& a, const foo& b) {

Answer 3

您应该将迭代器（指针的广义超集）传递给 STL sort 函数：

std::sort(fooarray, fooarray + end, &aGreaterThanb);

Answer 4

它已经按照您想要的方式工作了：

#include <algorithm>
int main()
{
    foo     data[10];
    std::sort(&data[0], &data[10], aGreaterThanb);
}

但是您有语法错误。您缺少一个大括号：

        return true;
} // <--- Missing this line
else
    return false;

为了提高效率，您应该通过 const 引用传递：

bool aGreaterThanb(foo const& a, foo const& b){

Answer 5

请注意，在最坏的情况下，排序函数最多进行 N^2 次比较。
stable_sort复杂度在N*logN和N*(LogN^2)之间

Answer 6

让它成为一个运营商。

struct foo {
    double num;
    std::string s;
};

bool operator>(const foo& a, const foo& b) {
    return (
        (a.num > b.num) ||
        ((a.num == b.num) &&
        anotherOutsideComparison(a.s, b.s))
    );
}

// note: std::sort expects operator<
bool operator<(const foo& a, const foo& b) {
    return b > a;
}

如果您确实想使用 operator> 进行排序，请传递 std::greater() 作为函子。

std::sort(foos.begin(), foos.end(), std::greater<foo>());