c++ - std::is_sorted 和比较器要求误导？

Question

我在这里遇到了关于 is_sorted 的老问题:std::is_sorted and strictly less comparison?

在偶然发现使用成对比较器的单调性检查未通过测试的用例之后。我认为给出如下的 lambda 符合要求:它会返回 true(仅当)lhs 和 rhs 的两个元素都被排序

bool 
check_pair_sorted(std::vector<std::pair<int, int>>& vec)
{
    return std::is_sorted(vec.begin(), vec.end(),[](auto& lhs, auto& rhs){
            return (lhs.first < rhs.first) && (lhs.second < rhs.second);
            });
}

但是，如果我像这样拆分支票，真正的预期功能是可能的

bool check_separate_sorted(std::vector<std::pair<int, int>>& vec)
{
    return std::is_sorted(vec.begin(), vec.end(),[](auto& lhs, auto& rhs){
           return (lhs.first < rhs.first) ; })
        && std::is_sorted(vec.begin(), vec.end(),[](auto& lhs, auto& rhs){ 
           return (lhs.second < rhs.second) ; });
}

查看上面问题的答案，其中建议提前返回 false 可能是首选实现，难道不应该同样提出要求吗？

comp - comparison function object (i.e. an object that satisfies the requirements of Compare) which returns false if the first argument is not less than (i.e. is not ordered before) the second.

就此处订购而言，我可能会遗漏一些东西，但目前似乎无法全神贯注。

Answer 1

你的 check_pair_sorted正在做与 check_separate_sorted 不同的事情我想这就是困惑的根源。

这归结为如何精确措辞 std::is_sorted被定义为。对于每两个元素 a[i]和 a[j]其中 i < j :

• 它检查 a[j] < a[i]永远不会是真的
• 它不检查a[i] < a[j]永远是真的

(当然，聪明的算法会避免进行所有 O(n^2) 次比较)

上面那两个项目符号不一样!

对于简单的数字，如在其他 SO 问题中，序列 1 2 3 3 4 5满足前一点，不满足后一点。

您的情况也发生了类似的情况。考虑两对序列:{ {1,2}, {2,1} } .序列的元素不同，但它们不能与您的第一个 lambda 比较器进行比较 - 它返回 false在两个方向上。因此，为了算法的目的，这两个元素被视为等价，即使它们并不严格相等。

所以，is_sorted在你的里面 check_pair_sorted对于序列 { {1,2}, {2,1} } 将返回true ，因为它检查第一个要点而不是第二个。

请注意，相同的等效性问题会影响其他 STL 结构和算法。例如，如果您有一个 std::set , 你将无法同时拥有 {1,2}和 {2,1}其中的元素使用您的第一个 lambda 作为比较器。