标准::is_sorted严格来说比较少

Question

我不太了解std::is_sorted算法及其默认行为。如果我们查看 cpp首选项，它说默认情况下std::is_sorted使用 < 运算符。取而代之的是，我发现使用<=是很自然的。但我的问题是，对于以下数字列表：

1 2 3 3 4 5

它会返回true，即使3 < 3应该false。这怎么可能？

编辑：它似乎比我想象的更糟糕，因为在这种情况下传递std::less_equal<int>会返回错误......传递比较器函数时应用的条件是什么？

Answer 1

每 25.4/5：

序列相对于比较器进行排序comp如果有的话 迭代器i指向序列和任何非负整数n 使得i + n是一个有效的迭代器，指向 序列， comp(*(i + n), *i) == false .

所以，对于

1 2 3 3 4 5

对于所有n，std::less<int>()(*(i + n), *i)将返回false，而对于3 3，std::less_equal将返回true。

Answer 2

即使你只有<运算符，你也可以计算出两个数字是否等价，不一定相等。

if !(first < second) and !(second < first)
then first equivalent to second

此外，正如paxdiablo的解决方案实际上首先提到的，您可以将is_sorted实现为在列表中向上并不断检查<是否为真，如果它是真的，你就停止。

这是函数的正确行为，来自 cplusplus.com

template <class ForwardIterator>
  bool is_sorted (ForwardIterator first, ForwardIterator last)
{
  if (first==last) return true;
  ForwardIterator next = first;
  while (++next!=last) {
    if (*next<*first)     // or, if (comp(*next,*first)) for version (2)
      return false;
    ++first;
  }
  return true;
}  

Answer 3

您似乎假设它正在检查(对于阳性情况(元素 N 是否小于元素 N+1 的所有元素栏最后一个。这确实不适用于仅<，尽管您可以使用"技巧"来评估<= <和!：以下两个是等价的：

if (a <= b)
if ((a < b) || (!((b < a) || (a < b)))) // no attempt at simplification.

但是，它更有可能检测到(负情况(元素 N 是否小于除第一个元素之外的所有元素 N-1，以便在发现违规后立即停止。这只能用<来完成，例如(伪代码(：

for i = 1 to len - 1:
    if elem[i] < elem[i-1]:
        return false
return true