将类的私有方法作为std::sort的比较运算符进行传递

Question

我正在编写一段代码来解决以下问题：给定一组数字 x[0], x[1], ..., x[N-1]，找到使它们按升序排列的排列。换句话说，我想在 {0,2,...,N-1} 上找到一个排列，如 i[0], i[1], ..., i[N-1]，使得 x[i[0]] <= x[i[1]] <= ... <= x[i[N-1]]。

为此，我已将 x 向量和索引向量 i（最初填充为 i[j] = j）存储为类的私有成员。我还定义了一个私有方法：

bool MyClass::compare(size_t s, size_t t) {
    return (x[s] < x[t]);
}

现在，我会像这样调用std::sort

std::sort(i.begin(), i.end(), compare);

我希望能够得到期望的结果。但是代码无法编译，出现以下错误：

error: no matching function for call to ‘sort(std::vector<long unsigned int>::iterator, std::vector<long unsigned int>::iterator, <unresolved overloaded function type>)’

我一定做对了，因为std::sort的文档也提到我可以将一个函数作为比较运算符传递给std::sort (http://www.cplusplus.com/reference/algorithm/sort/)。谢谢您的帮助。

- MikeL

---

cplusplus.com不是“文档”。那应该是C++标准。 - pattivacek

Answer 1

你的方法存在一些问题。最显然的是，你不能将成员函数用作自由函数。为了调用compare，你需要一个MyClass类型的对象和两个整数。在std::sort内部，实现会尝试使用仅有两个整数参数的自由（非成员）函数进行调用。

除此之外，你不能创建一个成员函数的指针而不显式地获取它的地址。对于成员函数，行std::sort(..., compare);将无法编译。虽然非成员函数将自动衰减为指向该函数的指针，但这里不是这种情况。

在C++11中，有两种不同的解决方案。最通用的方法是创建一个捕获this参数的lambda表达式：

std::sort(std::begin(i),std::end(i),
          [](int x, int y) { return compare(x,y); }); // or maybe even implement here

另一种方法是将对象和成员函数绑定到一个函数对象中：

std::sort(std::begin(i),std::end(i),
          std::bind(&MyClass::compare,this,_1,_2));

在最后一个案例中，std::bind函数会创建一个实现operator()的对象，该对象需要两个参数，并在指向this的对象上调用成员函数MyClass::compare。

这两种方法的语义略有不同，但在这种情况下你可以使用任意一种。

- David Rodríguez - dribeas

---

非常感谢您提供的详细信息。所以，正如您所提到的，这两种方法都只适用于C++11。是否有任何方法可以使代码也能够在旧版本的C++编译器中编译？（我猜如果我使用boost::bind而不是std::bind，第二种方法应该是可行的） - MikeL

@ManiBastaniParizi: 是的， boost::bind 是第二种方法的替代品。如果您只使用了一次，并且确实需要在没有C++11或boost::bind的情况下使其工作，则可以编写一个小的函数对象，它存储对象指针，接受两个参数并分派到相应的函数（手动实现lambda）。 - David Rodríguez - dribeas

Answer 2

请记住实例方法有一个隐含的第一个参数 - 对象的this指针。因此，您的比较运算符不是std::sort预期的类型 - 它需要三个参数而不是预期的2个。使用bind函数来解决这个问题（例如boost::bind）。例如，可以参考this question。

- Ivaylo Strandjev

---

谢谢你的帮助。那么隐式的 this 指针是第一个参数还是最后一个参数？另外，使用 std::bind 而不是 boost::bind 不是也可以吗？ - MikeL

是的，这是可能的 - 这就是我说“一个”绑定函数的原因。而且，对于实例方法，this指针是隐式的第一个参数。 - Ivaylo Strandjev

请注意，无论this指针是第一个、最后一个还是中间的位置，都是实现定义的[尽管我知道所有的实现都将其作为第一个]，而且这并不重要，因为您不能仅仅通过在适当的位置传递指针来调用成员函数。除了展开自己的汇编代码之外，参数的顺序是无关紧要的。 - David Rodríguez - dribeas

Answer 3

解决这个问题的一种方法是在你的类中定义一个函数调用运算符（在这里查看）：

bool MyClass::operator() (size_t s, size_t t) {
    return (x[s] < x[t]);
}

然后你可以像这样调用sort()方法：

sort(i.begin(), i.end(), *this);

- cpp

---

这可能相当昂贵，比较器是按值传递的。 - jrok

尽管这样会让它编译通过，但它涉及创建（至少一个）*this 的副本，这可能很昂贵。如果在C++11中采用此方法，您可以传递std::ref(*this)而不是*this以获得更便宜的副本（在C++03中，您也可以使用boost）。 - David Rodríguez - dribeas

Answer 4

我只是想评论一下@dribeas的答案对我没有用。我正在使用lambda函数，所以我不得不编辑它：

 std::sort(MyVector.begin(), MyVector.end(),
      [this](int x, int y) { return compare(x,y); });

- Quarktum