我能否防止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);

但是即使使用这种方式，复制仍然会发生。 有没有一种方法可以防止复制，还是说我必须让比较器只储存指向重要数据的指针？（我认为我们不能在我们的编译器版本中使用lambda/闭包）。

- Gnurfos

---

你能使用std::ref吗？ - Mat

不要让比较器存储数值，只需让它引用映射表即可。 - Kerrek SB

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

- David Rodríguez - dribeas

---

我更倾向于使用std :: ref，它的样板代码要少得多 :) 为什么实现需要复制比较器？我会说如果您传递一个引用，它可以从函数传递给函数。 - Gnurfos

std::ref 的设计正是为了解决这个问题。 - Marshall Clow

好的回答，但让我想知道为什么标准没有规定比较对象是通过常量引用而不是按值传递。除非比较器在调用时修改自己的状态的情况非常不可能，否则我几乎看不到任何不希望通过引用传递的情况。 - Marc van Leeuwen

@MarcvanLeeuwen：您可以始终使用类似于std::ref的东西在接受值的接口上获得引用语义，但是您无法从接受引用的接口中获得值语义。我不确定在创建这些接口时，在参数为函数名（在值情况下会衰减为指向函数的指针，在引用情况下，我不确定const是否会有问题）的情况下对接口的const Cmp＆的影响。 - David Rodríguez - dribeas