std::sort与自定义比较器

Question

在下面的代码中，为什么所有三个 IntComparator()、IntComparator2 和 IntComparator3 都可以作为 sort() 函数的第三个参数？它们不应该具有不同的左值函数类型吗？根据 https://en.cppreference.com/w/cpp/algorithm/sort 上所述，

比较函数的签名应等价于以下方式：

bool cmp(const Type1 &a, const Type2 &b);

这似乎更符合 IntComparator2 的要求？

此外，哪种方法更可取？第三个选项似乎更简单直观。

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

struct IntComparator
{
  bool operator()(const int &a, const int &b) const
  {
    return a < b;
  }
};

bool IntComparator2 (const int &a, const int &b)
{
    return a < b;
}

bool IntComparator3 (int a, int b)
{
    return a < b;
}

int main()
{
    int items[] = { 4, 3, 1, 2 };
    std::sort(items, items+4, IntComparator());

    for (int n=0; n<4; n++) {
        std::cout << items[n] << ", ";
    }

    std::cout << "\n";

    int items2[] = { 4, 3, 1, 2 };
    std::sort(items2, items2+4, IntComparator2);

    for (int n=0; n<4; n++) {
        std::cout << items2[n] << ", ";
    }

    std::cout << "\n";

    int items3[] = { 4, 3, 1, 2 };
    std::sort(items3, items3+4, IntComparator3);

    for (int n=0; n<4; n++) {
        std::cout << items3[n] << ", ";
    }

    std::cout << "\n";

    return 0;
}

- BYS2

---

我刚刚阅读了上面给出的参考资料；表述“应该等同于”确实有些含糊不清。 - Codor

@Codor 标准规定：“假定comp不会通过解引用的迭代器应用任何非常量函数。”你可能可以使用bool IntComparator3 (int &a, int &b)，但如果a或b被修改，则行为未定义。 - Caleth

@Caleth 我们最近禁止了那个。 - T.C.

Answer 1

std::sort 接受一个 functor。这是任何可以调用的对象（带有正确的参数）。该函数通过使用模板来实现，如下所示：

template<typename Iter, typename Comp>
void sort(Iter begin, Iter end, Comp compare) { ... }

IntComparator1、2和3都是这个比较器的有效functor，因为它们都可以使用operator()来调用2个整数。

就像您所说的那样，第三个选项通常更加直观。

- MivVG

---

Lambda表达式是另一种选择，可能更加直观。 - Steve

对，我一时忘记了那些:D Lambdas通常确实更好。 - MivVG

只要它们保持简短、相对自我解释（并且假设它们在您的代码中没有其他用处），就可以。 - Steve

第一个（函数对象）和 lambda 表达式都有一个显著的好处，那就是非常有可能被内联到 std::sort 算法实现中，而另外两个则是指向函数的指针，不太可能实现这一点。这可以极大地提高性能。因此，函数对象或 lambda 表达式应该是优先考虑的选择。 - WhozCraig

从技术上讲，函数不是对象，但它们会衰变为指向函数的指针，而指针是对象。 - Caleth

Answer 2

sort()函数在需要比较时会调用您提供的比较器函数。您的比较器如何获得其参数（值、引用、const引用）并不是sort()关心的，它将以相同的方式调用它（传递两个相同类型的参数），无论您的比较器在内部如何获得其参数。
从比较器定义的外部来看，这是不可感知的，因为我们调用这三个函数的方式完全相同。

唯一要求的是比较器只需要使用两个参数，并且它们必须与要排序的元素具有相同的类型。

但是，通过const引用传递更好，因为您的比较器保证不修改所比较的参数，并且避免了无用的复制（提高性能）。这就是为什么他们写下“应该是等价的”（这与“必须是等价的”不同）。

- Fareanor

---

你错过了一个细节，比较器不允许修改参数，否则 sort 无法按预期工作。这并不意味着参数不能作为非 const 引用传递，但如果是这样，则比较器 必须不 修改它们。 - 463035818_is_not_a_number

@formerlyknownas_463035818 当然可以！你说得完全正确。但是，如果用户提供了一个修改参数的比较器，那么这完全是用户的错误，sort() 对此不负责任。 - Fareanor

我指的是“唯一要求的是比较器不修改其参数...”，我并不完全同意，sort有责任说明前提条件，而比较器不修改其参数只是其中之一。 - 463035818_is_not_a_number

Answer 3

它们是等效的，因为C++规范表明它们都符合二元谓词的要求。以下摘录似乎是相关的。

[function.objects]

20.14.1 函数对象类型是可以作为函数调用中后缀表达式的类型的对象类型（参见[expr.call]，[over.match.call]）。函数对象是函数对象类型的对象。在预期将指向函数的指针传递给算法模板的位置上，接口被指定为接受一个函数对象。这不仅使算法模板能够使用指向函数的指针，而且还使它们能够使用任意的函数对象。

[alg.sorting]

25.7.2 Compare是一个函数对象类型（[function.objects]），符合名为BinaryPredicate（[algorithms.requirements]）的模板参数的要求。将类型为Compare的对象应用于函数调用操作时，上下文转换为bool([conv])后的返回值为true，如果调用的第一个参数小于第二个参数，则返回true，否则返回false。在假定有序关系的算法中，比较函数对象Compare comp被广泛使用。

[algorithms.requirements]

当没有其他限制时，BinaryPredicate参数用于期望函数对象的算法，该函数对象在将其应用于解引用两个对应迭代器的结果或在将其应用于解引用迭代器和类型T（当T是签名的一部分时）时返回可测试为true的值。换句话说，如果一个算法以BinaryPredicate二元谓词作为其参数，并以first1和first2作为其迭代器参数，具有相应的值类型T1和T2，则它应该在上下文转换为bool（[conv]）的构造binary_ pred（* first1，* first2）中正确工作。除非另有规定，否则BinaryPredicate始终将第一个迭代器的value_type作为其第一个参数，也就是在那些T value是签名的一部分的情况下，它应该在上下文转换为bool（[conv]）的构造binary_ pred（* first1，value）中正确工作。binary_ pred不得通过解引用的迭代器应用任何非常量函数。给定类型为（可能是const的）T1的glvalue u，该glvalue指定与* first1相同的对象，以及类型为（可能是const的）T2的glvalue v，该glvalue指定与* first2相同的对象，则binary_ pred（u，* first2），binary_ pred（* first1，v）和binary_ pred（u，v）都应该是等于binary_ pred（* first1，* first2）的有效表达式。binary_ pred（u，value）应该是等于binary_ pred（* first1，value）的有效表达式。

关于哪种更好的问题，我认为这是基于个人观点的，除非在您的具体情况下，分析表明其中一种更好。

- acraig5075