C++标准中对<>的全局不等式比较

Question

根据cppreference:

在不等式比较(<,>)中,首先比较第一个元素,并且只有当不等式比较不适用于它们时,才比较第二个元素.

这意味着:

return ((a.first < b.first) || (!(b.first < a.first) && (a.second < b.second)));

我的问题是,为什么它如此不直观？它背后的原因是什么？是否存在这种推理导致正确答案的例子？

我认为实施将只是:

return a.first < b.first && a.second < b.second

Answer 1

这种比较称为词典排序,是将两种不同排序合二为一的更自然的方式之一.

C++中请求的排序称为严格弱排序.这意味着以下内容应该成立:

• 无反射性: x <x始终为假.
• 传递性:如果x <y且y <z,则x <z.
• 反对称:如果x <y,那么y <x总是假的.
• 等价的传递性:如果x和y是无法比较的并且y和z是无法比拟的,那么x和z是无法比拟的.

这些属性是您需要的,以确保您可以获取对象列表并将它们按升序排序.这意味着您可以使用std::sort它们,或将它们存储在std::set.

您可以通过一些数学证明,如果您有两个不同的严格弱排序,那么通过组合它们得到的词典排序std::pair也是一个严格的弱排序.字典顺序是你可以将严格的弱顺序结合起来制定新的严格弱顺序的少数方法之一.

但是,您建议的顺序不是严格的弱排序,会导致某些假设中断.特别是,考虑对(0,5),(3,3)和(1,6).然后(0,5)与(3,3)无法比较,并且(3,3)与(1,6)无法比较.然而,我们确实有(0,5)<(1,6),这打破了等价的传递规则.因此,许多假设等价是可传递的排序算法(包括大多数主要的排序算法)将无法在您的范围内正常工作,这意味着std::sort可能表现不正确.这也意味着你也无法将它们存储在a中std::set,因为它std::set会以某种排序顺序(通常是平衡的二叉搜索树)存储所有内容,并且你可能会得到完全错误的结果.

希望这可以帮助!

Answer 2

如果a.first小于b.first,则该对已经少了.没有理由比较第二部分.对于第一部分,第一部分隐含地排序,就像名字首先按其第一个字母排序一样."Apple"出现在"Zebra"之前,因为"A"出现在"Z"之前,我们根本不将"p"与"e"进行比较.

所以,如果a.first < b.first,我们已经完成了.但是,如果没有,我们就没有完成.还有另一种方式a可以少于b.如果b.first < a.first不是这样的话,那就是a.second < b.second.

类比将是"Zebra"和"Zyman"."Z"不小于"Z",但"e"小于"y",因此第一次小于第二次.

您有时会看到它以这种方式编码:

bool operator<(const foo& a, const foo& b) {
 if (a.first < b.first) return true;
 if (a.first > b.first) return false;
 return (a.second < b.second);
}

我发现直觉上这个更容易理解,但逻辑是一样的: