Can I prevent std::sort from copying the passed comparison object

Question

We're using a comparator object to sort a vector:

std::vector<Data> v = ....
Comparator c = ....
std::sort(v.begin(), v,end(), c);

However, this makes copies of c during the sorting, and is causing performance problems, because Comparator objects store a big map (in which lookups are done when calling the comparison function). I thought I could force the use of references with:

const Comparator &ref = c;
std::sort(v.begin(), v.end(), ref);

but copies still happen with this. Is there a way to prevent copies, or do I have to make the Comparator store only pointers to heavy data ? (I don't think we can use lambda/closures with our compiler version).

Answer 1

The first thing to note is that the standard provides very little guarantees as of how many copies will be done for function objects. If you need to use state-full functions you should use reference semantics (have the state pointed to by the functor, rather than held inside).

That being said, the first alternative is to refactor the functor or to wrap it:

struct Wrapper {
   Comparator *cmp;
   Wrapper(Comparator *cmp) : cmp(cmp) {}
   bool operator()(T const & lhs, T const & rhs) const {
      return (*cmp)(lhs,rhs);
   }
};
Comparator cmp(...);
Wrapper w(&cmp);
sort(v.begin(), v.end(), w);

This is actually the same you would be getting if you use std::ref (C++11) directly:

Comparator cmp(...);
sort(v.begin(), v.end(), std::ref(cmp));