通过引用传递比较器函数 (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...\n";
    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.\n";

    arrayPrint();

    return 0;
}

谢谢您的帮助。

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

对于具有昂贵复制构造的较大类型，您可以更改（原始代码减去不必要的括号）：

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

to:

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

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

What will发挥作用，无论规模大小class问题是用函子（或 lambda，函子的语法糖）替换原始函数。std::sort将模板专门化为type比较器的类型，函数本身不是类型；它们实际上是共享相同原型的一组函数的实例。因此，如果您同时实现：

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 and compareReverse在你的程序的不同点，它只进行一种专业化std::sort for bool (*)(const arrMember&, const arrMember&)，并且该单一特化实际上必须通过指针传递并调用所提供的函数；调用函数的成本明显高于执行比较本身的微不足道的成本，并且通过指针调用通常更昂贵。

相比之下，函子（和 lambda）是独特的类型，因此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; });

无论哪种方式，代码都会运行得更快；上帝螺栓表演 https://godbolt.org/z/E3BJkJ这两种函数指针方法几乎是相同的，而使用函子方法，相对于函数指针方法，您可以将运行时间减少大约三分之一（在这种情况下，可以节省更多的值传递，但几乎不值得考虑）大多数时候；我会默认路过const参考，并且只有在分析表明速度很慢并且类型足够简单以至于按值传递可能会有所帮助时才考虑切换）。

模板和函子的这种好处就是 C++ 的原因std::sort可靠地击败Cqsort当使用得当时； C 缺乏模板，因此无法专门化qsort无论如何，并且必须始终通过函数指针调用比较器。如果你使用std::sort有了函数，并没有真正的改进qsort，但与函子/lambda 一起使用，它会生成much更快的代码以生成为代价more代码（独特的专业化std::sort对于每个函子/lambda）。通过复制粘贴实现的代码，您可以在 C 中获得相同的好处qsort，摆脱比较器并自己内联比较，但这是一个lot维护费用； C++ 模板为您完成 99% 的工作，您只需要记住对回调使用函子/lambda，而不是原始函数。