我可以阻止std :: sort复制传递的比较对象

Question

我们使用比较器对象来对矢量进行排序:

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

但是,这会在排序过程中生成c的副本,并导致性能问题,因为Comparator对象存储一个大的映射(在调用比较函数时会进行查找).我以为我可以强制使用引用:

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

但副本仍然会发生.有没有办法防止复制,或者我是否必须使Comparator只存储指向重数据的指针？(我认为我们的编译器版本不能使用lambda/closures).

Answer 1

首先要注意的是,标准对于为函数对象执行的副本数量提供的保证非常少.如果你需要使用状态完整函数,你应该使用引用语义(让函子指向状态,而不是保持在里面).

话虽这么说,第一个选择是重构仿函数或包装它:

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

这实际上与您std::ref直接使用(C++ 11)时所获得的相同:

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