Q:

Passing object to compare function makes sorting slow?

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? 

A:

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.

A:

std::ref is a pointer in disguise. What the code does is that instead of copying a heavy-weight SortByFutureVolume object, it copies around the pointer to the same object - which is obviously much faster.
The option would be to make the Graph g a (const) reference inside the sorter object.

