通过引用传递比较器函数(C++11)

我正试图加速我的代码(下面是一个最小的、可重现的例子)，我被告知，对于我的比较器函数来说，通过引用传递将是一种更有效的方法。这是我第一次听说这个短语，所以我查了一下，找到了一些有例子的网站，但我不知道什么时候和如何使用它。在这种情况下我将如何使用它？

#include <array>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <ctime>
#include <random>

using namespace std;

class arrMember {
public:
    int var;
    arrMember(int var) :
        var(var) {}
    arrMember() {};
};

array<int, 1000000> arraySource;

array<arrMember, 1000000> arrayObjects;

bool compare(arrMember(x), arrMember(y)) {
    return (x.var < y.var);
}

void arrayPrint() {
    ofstream output("arrayPrint.txt");
    for (int k = 0; k != arrayObjects.size(); k++) {
        output << arrayObjects[k].var << endl;
    }

    output.close();
}

void sort() {
    int j = 0;
    for (auto i = arraySource.begin(); i != arraySource.end(); i++, j++) {
        arrayObjects[j] = arrMember(arraySource[j]);
    }

    sort(arrayObjects.begin(), arrayObjects.end(), compare);
}

int main(){
    random_device rd{};
    mt19937 engine{ rd() };
    uniform_int_distribution<int> dist{ 0, 9999 };
    for (int x = 0; x < arraySource.size(); ++x){
        arraySource[x] = dist(engine);
    }

    cout << "Executing sort...
";
    clock_t t1 = clock();
    sort();
    clock_t t2 = clock();
    double timeDiff = ((double)(t2 - t1)) / CLOCKS_PER_SEC;

    cout << "Sort finished. CPU time was " << timeDiff << " seconds.
";

    arrayPrint();

    return 0;
}

谢谢您的帮助。

---

解决方案

对于很小的类型，通过引用传递没有帮助；复制构造一个由单个int组成的类的成本基本上与获取现有实例的地址相同，而复制构造意味着比较器不需要取消引用指针来查找值，它已经在本地堆栈上了。

对于复制构造成本较高的较大类型，您可以更改(原始代码减去不必要的括号)：

bool compare(arrMember x, arrMember y) {
    return x.var < y.var;
}

收件人：

bool compare(const arrMember& x, const arrMember& y) {
    return x.var < y.var;
}

并获得有意义的加速，但对于一个简单的int包装类，您什么也得不到。

无论所讨论的class的大小如何，将产生影响的是用函数器(或lambdas，这是函数器的语法糖)替换原始函数。std::sort将模板专用于比较器的类型，而函数本身不是类型；它们实际上是共享相同原型的一组函数的实例。因此，如果您同时实现这两个功能：

bool compare(const arrMember& x, const arrMember& y) {
    return x.var < y.var;
}
bool compareReverse(const arrMember& x, const arrMember& y) {
    return x.var > y.var;
}

和std::sort在程序中的不同位置使用compare和compareReverse调用std::sort，它只对std::sortforbool (*)(const arrMember&, const arrMember&)进行一次专门化，而且这一专门化实际上必须通过指针传递和调用所提供的函数；调用函数的成本远远高于执行比较本身的微不足道的成本，通过指针调用通常更昂贵。

相比之下，函数器(和lambdas)是唯一的类型，因此std::sort可以完全专门化它们，包括内联比较，因此不会发生对比较器函数的调用；比较器逻辑直接内联到std::sort的唯一专门化。因此，不是：

bool compare(const arrMember& x, const arrMember& y) {
    return x.var < y.var;
}
std::sort(..., compare);

您可以这样做：

struct compare {
    bool operator()(const arrMember& x, const arrMember& y) const {
        return x.var < y.var;
    }
};
std::sort(..., compare());

或将整个代码内联为C++11 lambda：

std::sort(..., [](const arrMember& x, const arrMember& y) { return x.var < y.var; });

无论哪种方式，代码都会运行得更快；Godbolt shows这两种函数指针方法基本相同，而使用函数式方法，您可以将运行时间相对于函数指针方法减少约三分之一(在这种情况下，通过值传递节省了一点时间，但大多数时间几乎不值得考虑；我将默认通过const引用传递，并且只有当分析表明它很慢，并且类型足够简单，通过值传递可能会有所帮助时，才考虑切换)。

模板和函数器的这一好处就是C++的std::sort在正确使用时可靠地击败C的qsort的原因；C缺乏模板，所以它根本不能专门化qsort，必须始终通过函数指针调用比较器。如果将std::sort与函数一起使用，它与qsort相比并没有真正的改进，但与函数/lambda一起使用时，它会生成快得多的代码，但代价是生成更多的代码(为每个函数/lambda使用std::sort的唯一专门化)。通过复制粘贴实现qsort的代码，去掉比较器并自己内联比较，您可以在C中获得同样的好处，但这是一大维护开销；C++模板为您完成了99%的工作，您只需记住使用函数器/lambda进行回调，而不是原始函数。