c++ - std::is_sorted 和严格较少的比较？

Question

我不太了解std::is_sorted算法及其默认行为。如果我们查看cppreference，它会说默认std::is_sorted使用<运算符。相反，我发现使用<=会很自然。但我的问题是以下数字列表：

1 2 3 3 4 5

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

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

Answer 1

Per 25.4/5:

A sequence is sorted with respect to a comparator comp if for any iterator i pointing to the sequence and any non-negative integer n such that i + n is a valid iterator pointing to an element of the sequence, comp(*(i + n), *i) == false.

So, for

1 2 3 3 4 5

std::less<int>()(*(i + n), *i) will return false for all n, while std::less_equal will return true for case 3 3.

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 的所有元素（最后一个除外）。这确实不适用于 just <，尽管您可以使用“技巧”来评估and ：<=以下两个是等效的：<!

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

However, it's far more likely that it detects (the negative case) if element N is less than element N-1 for all but the first so that it can stop as soon as it finds a violation. That can be done with nothing more than <, something like (pseudocode):

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