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) ; });
}

看看上面问题中的答案，建议早期返回虚假可能是首选实施，不应该同样提出要求吗？

comp - 比较函数对象（即满足Compare要求的对象），如果第一个参数不小于第二个参数（即之前没有排序），则返回false。

我可能会在这里订购方面遗漏一些东西，但目前似乎无法绕过它。

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，你将无法使用你的第一个lambda作为比较器同时包含{1,2}和{2,1}元素。

Answer 2

std::is_sorted在比较函数 - 运算符方面明确定义

但是，如果以这种方式构造比较函数，那2个元素没有明确的关系 - 即a <b和b <a都是真的 - 那么任何排序或排序操作的结果都不能完全定义。

这是混乱的真正根源。

Answer 3

对于词法排序，您需要：

return (lhs.first < rhs.first) || ((lhs.first == rhs.first) && lhs.second < rhs.second));