c++ - 在 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)”(运算符 <= 甚至不需要定义；同样适用于 operator== )。

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

请注意，sorted 未定义为:“每当迭代器 it 和 it + 1 在 [first, last) 中时，*(it + 1) < *it 的计算结果为 false。”

显然，如果一个范围被排序，那么它是非递减的。 如果 比较器 comp是 total order那么很容易看出，如果一个范围相对于 comp 没有减少然后它相对于 comp 进行排序.但如果 comp不是总顺序，那么如果范围相对于 comp 不减少，它是否仍然一定是正确的然后它相对于 comp 进行排序?

请注意，对 comp 的唯一要求是它满足比较要求:https://en.cppreference.com/w/cpp/named_req/Compare .
特别是comp不需要是全序(但是，该页面上描述的诱导等价类将在由 comp 诱导的顺序下形成全序)。

为什么这个问题很重要:

我没有反例，但我怀疑答案是否定的，因为否则标准为什么会区分排序和非增加的术语？ (更新:答案是 是的 )。例如，使用 std::inpace_merge , 两个输入 ranged 需要排序，但输出 range 只要求非递减(标准没有说 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):

If (last - first) < 2 returns last. Otherwise, returns the last iterator i in [first, last) for which the range [first, i) is sorted.

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

例如，该标准基本上规定 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

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

如果序列是 非递减 ，然后 comp(*it, *(it - 1))总是假的。

所以，!comp(*it, *(it - 1))永远是真的。

如 !comp是可传递的，那么 !comp(*(it + n), *it)也永远如此。

在这种情况下，comp(*(it + n), *it)总是假的，所以序列是 已排序 .

比较器 comp(x, y)必须是 strict weak ordering . “严格弱阶的补是全预阶”( Wikipedia)是一个数学定理，全预阶是可传递的，所以 !comp的要求性质在上述证明的第 3 步中成立。

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