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

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 的向量运行上述代码时，它会在几分之一秒内完成。然而，当我在我的 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

你应该有一个只读的or if ，而不是有一个Graph数据成员。这样，无论何时被复制，都不会被复制。SortByFutureVolumeGraph &const Graph &gSortByFutureVolumeGraph

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指针，则变为可复制分配，因为可以分配指针但不能分配引用。那会给你GraphSortByFutureVolume

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它是为实现而保留的，因此它是无效的标识符。