在 C++17 中，即使使用不是全序的比较器，非递减也一定意味着排序吗？

Question

在 C++17（标准 ISO/IEC 14882:2017(E)）中，已排序和非递减的术语不相同：

的序列[first, last)被说成是在非递减次序相对于一个比较器comp，如果为任何迭代器it在[first, last)比其他first的条件comp(*it, *(it - 1))（即，*it < *(it - 1)）的计算结果为false。（参见 ISO/IEC 14882:2017(E) 28.7.5 第 1035 页）

请注意，非递减不是定义为：“每当迭代器it和it + 1在[first, last)然后*it <= *(it + 1)”（运算符 <= 甚至不需要定义；同理 for operator==）。

的序列被说成是排序相对于一个比较器comp，如果为任何迭代器it指向序列和任何非负整数n，使得it + n是一个有效的迭代器指向序列的元素，comp(*(it + n), *it)计算结果为false。（参见 ISO/IEC 14882:2017(E) 28.7 p. 1028）

需要注意的是排序没有被定义为：“每当迭代器it并it + 1在[first, last)随后*(it + 1) < *it的计算结果为假。”

显然，如果一个范围被排序，那么它是非递减的。如果比较器comp是一个全序，那么很容易看出，如果一个范围相对于 不递减，comp那么它是相对于 进行排序的comp。但是，如果comp不是全序，那么如果一个范围相对于非递减，comp那么它是相对于排序的，它仍然一定是真的comp吗？

请注意，唯一的要求comp是它满足比较要求：https : //en.cppreference.com/w/cpp/named_req/Compare。具体地讲，comp是不要求是全序（但是，在该网页上所描述的诱导等价类将形成顺序的下一个总订单诱导通过comp）。

为什么这个问题很重要：

我没有反例，但我怀疑答案是否定的，因为否则标准为什么会区分sorted和non-increasing的术语？（更新：答案是肯定的）。例如，使用std::inpace_merge，需要对两个输入范围进行排序，但仅要求输出范围是非递减的（标准没有说必须对 的输出范围std::inpace_merge()进行排序）。

我问的原因是因为如果这不是真的，那么许多std算法的许多 STL 实现似乎都会出现问题。

请注意，std::is_sorted_until在libstdc++和libc++ 中的实现方式相同；它们本质上是这样的：

template <class ForwardIt, class Compare>
ForwardIt is_sorted_until(ForwardIt first, ForwardIt last, Compare comp) 
{
    if (first != last) {
        ForwardIt next = first;
        while (++next != last) {
            if (comp(*next, *first))
                return next;
            first = next;
        }
    }
    return last;
}

注意到问题了吗？这些实现std::is_sorted_until() 查找最长的非递减范围而不是查找最长的排序范围。标准要求std::is_sorted_until(first, last)（ISO/IEC 14882:2017(E) 28.7.1 p. 1031）：

如果(last - first) < 2返回last。否则，返回最后迭代i中[first, last)针对的范围内[first, i)进行排序。

因此，如果在一般情况下，非递减范围并不一定意味着范围已排序，那么这些实现不符合标准。这会产生下游效应。

例如，该标准基本上规定std::is_sorted()应定义为：

template<class ForwardIt, class Compare>
bool is_sorted(ForwardIt first, ForwardIt last, Compare comp)
{
    return std::is_sorted_until(first, last, comp) == last;
}

这意味着std::is_sorted()还要检查非递减范围的定义，而不是检查排序范围的定义。

现在标准中对输出有什么要求std::merge()？那么如果输出范围是[d_first, d_last)那么标准的要求是“范围分别满足std::is_sorted(d_first, d_last)或std::is_sorted(d_first, d_last, comp)”。（ISO/IEC 14882:2017(E) 28.7.5 第 1035 页）

这就是为什么知道这个问题的答案很重要。（此外，这将有助于我尝试测试一些算法）。

Answer 1

考虑比较器的补码，即返回相反布尔结果的函数!comp(x, y)：

1. 如果序列是非递减的，则comp(*it, *(it - 1))始终为假。
2. 所以，!comp(*it, *(it - 1))永远是真的。
3. 如果!comp是可传递的，那么它!comp(*(it + n), *it)也总是正确的。
4. 在这种情况下，comp(*(it + n), *it)总是假的，所以序列是sorted。

比较器comp(x, y)必须是严格的弱排序。“严格弱阶的补是全预阶”（维基百科）是一个数学定理，全预阶是可传递的，因此!comp上述证明的第 3 步所要求的性质成立。

因此，对于满足严格弱排序要求的有效比较器，非递减和排序条件在逻辑上是等价的；因此is_sorted（仅检查相邻元素）的 STL 实现是正确的。