Passing object to compare function makes sorting slow?

Question

I had the following code in my program.

//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;
};

And then I use it for sorting like this:

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

When I run the above code on my mac computer for a vector of size 23K it completes in a fraction of seconds. However, when I run on my ubuntu 14 machine. It takes several minutes and it hasn't even completed yet.

I search for this problem and found the following solution here Can I prevent std::sort from copying the passed comparison object

Basically modifying my code as so fixes the problem:

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

After this the runtime on both my mac an ubuntu are comparable. Very much faster.

I know that this works but I'm trying to understand why? I know that slow code above was due to copying of graph and SortByFutureVolume. Why do you need std::ref()? Is this solution even correct and is there a better way to do this?

Answer 1

Instead of having a Graph data member in SortByFutureVolume you should have a Graph & or const Graph & if g can be read only. This way, anytime the SortByFutureVolume is copied the Graph is not copied.

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;
};

As pointed out by Benjamin Lindley in the comments if You change SortByFutureVolume to store a pointer to the Graph instead of a refernece then SortByFutureVolume becomes copy assignable as pointers can be assigned but references cannot. That would give you

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;
};

As a side not it is okay to have _g as a variable name in a function parameter as it does not start with a capital letter but it is a good habit to not use leading underscores. This is doubly true in the global space where _g would be an invalid identifier as it is reserved for the implementation.