c++ - 将对象传递给比较函数会使排序变慢？

Question

我的程序中有以下代码。

//Compare class
class SortByFutureVolume
{
public:
        SortByFutureVolume(const Graph& _g): g(_g){}

        bool operator() (const Index& lhs, const Index& rhs){
            return g.getNode(lhs).futureVolume() > g.getNode(rhs).futureVolume();
        }
    private:
        Graph g;
};

然后我用它来排序:

    std::sort(nodes.begin(), nodes.end(),SortByFutureVolume(g));

当我在我的 Mac 计算机上运行上面的代码以获得大小为 23K 的 vector 时，它会在几分之一秒内完成。但是，当我在我的 ubuntu 14 机器上运行时。这需要几分钟，甚至还没有完成。

我搜索这个问题并在这里找到了以下解决方案 Can I prevent std::sort from copying the passed comparison object

基本上修改我的代码就解决了这个问题:

SortByFutureVolume s(g);
std::sort(_nodes.begin(), _nodes.begin()+ end, std::ref(s));

在此之后，我的 mac 和 ubuntu 上的运行时间是相当的。非常快。

我知道这行得通，但我想了解为什么？我知道上面的慢代码是由于图形和 SortByFutureVolume 的复制。为什么需要 std::ref()？这个解决方案是否正确，是否有更好的方法来做到这一点？

Answer 1

SortByFutureVolume 中不应包含 Graph 数据成员，而应包含 Graph & 或 const Graph &如果 g 是只读的。这样，无论何时复制 SortByFutureVolume，都不会复制 Graph。

class SortByFutureVolume
{
public:
        SortByFutureVolume(const Graph& _g): g(_g){}

        bool operator() (const Index& lhs, const Index& rhs){
            return g.getNode(lhs).futureVolume() > g.getNode(rhs).futureVolume();
        }
    private:
        Graph& g;
        // or
        const Graph& g;
};

正如 Benjamin Lindley 指出的那样在评论中，如果您更改 SortByFutureVolume 以存储指向 Graph 的指针而不是 refernece，则 SortByFutureVolume 变为可复制分配，因为可以分配指针但是引用不能。那会给你

class SortByFutureVolume
{
public:
        SortByFutureVolume(const Graph& _g): g(&_g){}

        bool operator() (const Index& lhs, const Index& rhs){
            return g->getNode(lhs).futureVolume() > g->getNode(rhs).futureVolume();
        }
    private:
        const Graph * g;
};

另一方面，可以将 _g 作为函数参数中的变量名，因为它不以大写字母开头，但不使用前导下划线是一个好习惯。这在 _g 将是无效标识符的全局空间中是双重的，因为它是为实现保留的。