为什么std :: sort compare函数必须在参数相等时返回false？

Question

在std :: sort中,您可以提供第三个参数,该参数是对列表进行排序的基础.如果您希望第一个参数首先出现,则返回true.如果您希望第一个参数首先出现,则返回false.我遇到的问题是我的谓词函数应该是一个"无效的比较器",我已经将它缩小到它不符合以下要求的事实:

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

我已经看过一些术语,例如std :: sort需要"严格的弱排序".除了2个地方,我得到的关于这些主题的所有其他页面似乎都是技术论文,我无法理解.我能理解的是:

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

但对我来说,这也是"部分有序集合"的含义,它是:

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

而且,我无法理解其中任何一个中的"严格"含义.

撇开我对订单理论术语的困惑,我的问题是,如果在比较函数中,参数1和参数2是相等的,在这种情况下,我不关心哪一个先于另一个(之前的任何一个会让我开心),为什么我不能回归真的让争论1先来？

我还要问我的程序实际上是如何知道它是一个无效的比较器,但后来我认为它可能只是在比较函数返回true时检查arg1和arg2是否相等.

Answer 1

比较功能仅对“小于”运算符建模。考虑<运算符如何处理原始类型，例如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

退货true意味着您想a在此之前订购b。因此，false如果不是这种情况，则返回，要么是因为您想b在之前订购a，要么是因为它们的顺序无关紧要。

如果true在参数相等时返回，则表示您a要先于b而又b要先于a，这是一个矛盾。

Answer 2

1.从代码角度

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

以下代码是快速排序中的__unguarded_pa​​rtition函数。

  /// 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，compare 函数返回true，那么__first迭代器会一直向右移动，程序就会越界，导致coredump。

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

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

2. 从算法逻辑的角度

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

!(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>>, Item21: Always have compare functions return false for equal values.

Answer 3

使用的算法std::sort未指定。通过使用不符合标准设置要求的比较函数，您会破坏算法的假设，并导致未定义的行为。

看看这个嘈杂的比较函数的输出中会发生什么，它使用<= (which is not a valid compare)而不是< (which is valid)。

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 等）和向量范围之外的索引（在这种情况下为负索引）的值。