为什么当参数相等时，std::sort比较函数必须返回false？

Question

在std::sort函数中，你可以提供第三个参数作为排序列表的基础。如果你想让第一个参数排在前面，则返回true。如果你想让第二个参数排在前面，则返回false。我遇到了一些问题，我的谓词函数被称为“无效比较器”，并且我已经缩小了问题范围，发现它没有满足以下要求：

if arg1 == arg2, compare function MUST return false.

我看到一些术语，例如std::sort需要“严格弱序”。除了两个地方，我获取的所有关于这些主题的页面似乎都是技术论文，我无法理解它。我所能理解的是：

In weak ordering some elements "may be tied" with each other.

但对我来说，这也是“偏序集”的意义，即：

"there may be pairs of elements for which neither element precedes the other"

此外，我无法理解它们中的任何一个中“strict”的意思。

撇开我对序列理论术语的困惑，我的问题是如果在比较函数的参数1和参数2相等的情况下（在这种情况下，我不关心哪个排在前面（排在前面的都可以使我满意），为什么我不能返回true让参数1排在前面？

我还想问一下我的程序如何知道它是无效的比较器，但后来我想可能只是检查当比较函数返回true时arg1和arg2是否相等。

- Zebrafish

---

请注意，没有检查来验证您的比较器是否满足严格弱序的要求。 - Rakete1111

“@Rakete1111: 这是什么意思？如果实现方愿意，它们可以自由进行这样的检查。 实际上，一些实际的实现确实这样做。” - AnT stands with Russia

在 Visual Studio 中，它会抛出一个异常，说“无效比较器”。我认为要么它显式地检查了，要么排序算法中的某些东西出了问题并抛出了异常。 - Zebrafish

@AnT 真的吗？我的意思是在某些实现中（例如gcc/clang），它们只是假定要求已经满足，如果没有满足，则会得到一些奇怪的顺序。 - Rakete1111

@Rakete1111：不一定。如果要求未得到满足，则行为是未定义的。在现实生活中，它可以表现出许多方式，不仅限于“一些奇怪的顺序”。它也很容易导致越界访问。防止这种情况需要额外的检查，据我所知，GCC/Clang没有实现。因此，我认为你观察到的那些“奇怪的顺序”纯粹是由于运气而产生的。在现实生活中，它也可能因为越界访问而崩溃。 - AnT stands with Russia

Answer 1

比较函数简单地模拟了一个“小于”操作符。考虑一下对于像整型（int）这样的基本类型，<操作符是如何工作的：

比较函数简单地模拟了一个“小于”操作符。考虑一下对于像整型（int）这样的基本类型，<操作符是如何工作的：

int a = 1, b = 2;     a < b == true      a is less than b
int a = 2, b = 1;     a < b == false     a is not less than b, because a is greater than b
int a = 1, b = 1;     a < b == false     a is not less than b, because a equals b

如果您希望将 a 排在b 的前面，则返回true。因此，如果不是这种情况，请返回false，无论是因为您想要将b 排在a 前面，还是因为它们的顺序无关紧要。

如果在参数相等时返回true，则表示您希望a排在b之前，同时又希望b排在a之前，这是矛盾的。

- Oktalist

---

我不确定为什么它意味着我想要那个。是因为在下一步中，比较将在相同的值上进行，除了它们将被反转的参数发送到比较函数吗？ - Zebrafish

@Zebrafish：这是定义问题。你似乎把事情搞反了：你不能随意实现它，然后告诉算法如何使用它——算法要求“给我一个严格的排序谓词”，而你需要实现它。在严格排序中，当a==a时，f(a, a) == false。 - GManNickG

Answer 2

1. 从代码角度来看

当元素数量大于 _S_threshold（在STL中，默认值为16）时，std::sort() 将使用 快速排序（quicksort）。

以下代码是快速排序中的 __unguarded_partition 函数。

  /// This is a helper function...
  template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
    _RandomAccessIterator
    __unguarded_partition(_RandomAccessIterator __first,
             _RandomAccessIterator __last,
             const _Tp& __pivot, _Compare __comp) 
   {
      while (true)
      {
        while (__comp(*__first, __pivot))
          ++__first;
        --__last;
        while (__comp(__pivot, *__last))
          --__last;
        if (!(__first < __last))
          return __first;
        std::iter_swap(__first, __last);
        ++__first;
      }
    }

如果 arg1 == arg2，比较函数返回 true，则 __first 迭代器将继续向右移动，程序将越界并导致核心转储。

while (__comp(*__first, __pivot))
    ++__first;

因此，如果arg1 == arg2，比较函数必须返回false。

2. 从算法逻辑的角度来看

如果比较函数使用operator<=，那么对于相等的值，它将返回true。 如果测试10B是否等同于10A，则自然使用比较函数。 在这个例子中，这是operator<=。 它检查这个表达式是否为真：

!(10A<= 10B)&&!(10B<= 10A) //test 10Aand 10B for equivalence

十进制数字10A和10B都是10，因此很明显10A <= 10B成立。同样明显的是，10B <= 10A也成立。因此上述表达式可以简化为

!(true)&&!(true)

并且这简化为

false && false

这种说法是错误的。也就是说，测试得出10A和10B不相等，因此不同。 此外，任何比较函数返回相等值为true的情况都会做同样的事情。 根据定义，相等的值并不等价！ 这不很酷吗？

您还可以参考<< Effective STL>>，条款21：始终使比较函数对于相等的值返回false。

- Terry

Answer 3

std::sort使用的算法是未指定的。如果使用不符合标准要求的比较函数，则会破坏算法的假设，并导致未定义的行为。请看使用<=（无效的比较符号）而不是有效的<的此嘈杂的比较函数的输出结果。 http://coliru.stacked-crooked.com/a/34e4cef3280f3728 在输出中，我打印了一个递增的变量（用于参考，以便指出算法何时失控），然后是第一个参数及其在向量中的位置，然后是第二个参数及其在向量中的位置。例如：

124: 2@12 <= 4@7

这意味着这是比较函数的第124次调用，它正在比较索引12处的值2和索引7处的值4。

从第37行开始，情况变得疯狂起来。

37: 0@0 <= 0@-1
38: 0@0 <= 144@-2
39: 0@0 <= 0@-3
40: 0@0 <= 192@-4

这段代码正在比较向量中我甚至没有插入的值（144、192等）和超出向量范围的索引（在这种情况下为负索引）。

- Benjamin Lindley

---

将比较符号更改为<，我仍然看到像93: 0@35180308044405 <= 0@0这样的行，因此位置计算似乎有些问题。 - Tor Arne

Answer 4

对于Benjamin Lindley的答案解释，考虑std::sort使用Hoare类型分区方案的快速排序的典型情况。使用compare(value, pivot)进行比较扫描左侧以查找小于pivot的值，而使用compare(pivot, value)扫描右侧以查找大于pivot的值。请注意，快速排序分区可能依赖于当左侧或右侧扫描遇到一个值== pivot时停止扫描并且不会在该扫描中继续扫描超过pivot。如果用户提供的compare函数在这种比较（value == pivot时为true）上返回true，则扫描可能会继续超出正在排序的数组或向量的边界，这显然是Benjamin Lindley测试用例中发生的情况。

- rcgldr

Answer 5

不深入数学，只需使用'<'运算符（或'>'运算符，如果您希望）即可比较2个变量。然而，在“严格弱序”解释和排序器实现中，通常使用'<'。

基本思想是，在实际编程中，如果a < b == false且b < a == false，那么a == b。

- Serge

Answer 6

TL;DR： 为什么当参数相等时，std::sort的比较函数必须返回false？

它必须返回false，因为没有必要对相等的参数进行排序。

解释

一个两路比较运算符函数检查是否希望在第一个数字之前返回第二个数字。所以如果是，应该返回true，否则返回false。

std::sort和许多其他库函数使用这样的运算符函数。

例如：

std::sort(my_container.begin(), my_container.end(), [](const MY_CLASS* lhs, const MY_CLASS* rhs) -> bool
{
    return lhs->m_level < rhs->m_level;
});

然而，当比较函数作为参数在这样的库函数中使用时，通常情况下，这些库函数会根据比较函数返回的true来执行相应的操作。因此，特别是在使用std::sort时，当参数为true时，std::sort将执行某些操作（例如重新排序）。

所以一般来说，当比较函数作为std库算法的参数使用时，如果算法需要执行某些操作，它应该返回true。反之，如果不需要执行任何操作，则应返回false。

- KeyC0de