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

问：

在 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 是相等的，在这种情况下，我不在乎哪个先于另一个（任何一个先于另一个都会让我高兴），为什么我不能返回 true 让参数 1 先出现？

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

C++ 排序 std

@Rakete1111：不一定。如果未满足要求，则行为未定义。在现实生活中，它可以以多种方式表现出来，不仅限于“一些奇怪的秩序”。它还很容易导致越界访问。防御这种情况需要额外的检查，而AFAIK GCC / Clang没有实施。因此，我认为您观察到的那些“奇怪的订单”纯粹是运气造成的。在现实生活中，它也可能因为越界访问而崩溃。

答：

18赞 Oktalist 8/29/2017 #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

退货意味着您希望在之前被订购。因此，如果不是这种情况，请返回，要么是因为您想在之前订购，要么是因为他们的订单无关紧要。trueabfalseba

如果你在参数相等时返回，那么你就是在说你想在前面，你想在前面，这是一个矛盾。trueabba

为了解释 Benjamin Lindley 的答案，请考虑 std：：sort 使用 quicksort 和 Hoare 类型分区方案的典型情况。使用 compare（value，pivot）扫描左侧的值<枢轴进行比较，而右侧使用 compare（pivot， value）扫描>枢轴的值。请注意，快速排序分区可能依赖于这样一个事实，即左扫描或右扫描在遇到值 == 透视时停止，并且不会继续扫描该扫描的透视透视。如果用户提供的比较函数在这样的比较中返回 true（当值 == 透视时为 true），则扫描可能会继续超出正在排序的数组或向量的边界，这显然是 Benjamin Lindley 的测试用例中发生的情况。

8赞 Terry 7/5/2019 #5

1. 从代码的角度来看

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

以下代码是快速排序中的__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， compare 函数返回 true，则迭代器将继续向右移动__first程序将超出范围并导致 coredump。

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

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

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

如果比较函数使用运算符<=，则对于相等的值，它返回 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 的比较函数都会做同样的事情。根据定义，相等值不是等价的！这不是很酷吗？

您还可以查看<<有效的 STL>>，Item21：始终让比较函数对相等值返回 false。

0赞 KeyC0de 6/6/2023 #6

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

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

解释

2 向小于比较功能检查是否要在第二个数字之前返回第一个数字。因此，如果是，或者如果不是，它应该返回。operator<truefalse

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

当比较函数在此类库函数中用作参数时，此类库函数通常根据比较函数的响应“行动”。因此，特别是，当参数为真时，将执行某些操作（即执行重新排序）。这与小于运算符（<）的典型行为一致，并且是此类排序算法（如）的预期行为。truestd::sortstd::sortstd::sort

所以一般来说，当比较函数被用作 std lib 算法的参数时，如果算法希望它做某事，它应该返回。反之亦然，当它不应该做任何事情时，它应该返回。truefalse

上一个：为什么这个 std：：vector：：emplace_back 失败？

下一个：如何传递对模板 typename 参数的引用

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

Why must std::sort compare function return false when arguments are equal?

评论

评论

评论