根据 cppreference :
In inequality comparisons (<, >), the first elements are compared first, and only if the inequality comparison is not true for them, the second elements are compared.
翻译成这样:
return ((a.first < b.first) || (!(b.first < a.first) && (a.second < b.second)));
我的问题是,为什么它如此不直观? 背后的原因是什么?有没有这种推理得出正确答案的例子?
我认为实现只是:
return a.first < b.first && a.second < b.second
最佳答案
这种比较称为 lexicographical ordering 并且是将两种不同顺序合并为一个的更自然的方法之一。
在 C++ 中请求的顺序称为 strict weak orderings 。这意味着以下内容应为真:
- 非自反性: 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
可能表现不正确。这也意味着您也不能将它们存储在 std::set
中,因为 std::set
在内部以某种排序顺序(通常是平衡二叉搜索树),你可能会得到完全错误的结果。
希望这对您有所帮助!
关于c++ - C++ 标准中 pair<> 的全局不等式比较,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8934629/