配对的全球不平等比较在 C++标准

发布于 2024-12-27 17:53:37 字数 523 浏览 1 评论 0原文

在不等式比较 (<, >) 中，比较第一个元素首先，并且只有当不平等比较对他们来说不成立时，比较第二个元素。

这可以翻译成这样：

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

我的问题是，为什么它如此不直观？ 其背后的原因是什么？有没有例子表明这种推理可以得出正确的答案？

我认为实现将很简单：

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

原文

As according to 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.

which translates to something like this:

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

My quesion is, why is it so unintuitive? What is the reasoning behind it? And are there examples where this reasoning leads to the correct answers?

I thought the implementation will simply be:

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

稍尽春風 2025-01-03 17:53:37

这种比较称为词典顺序，是一种将两种不同的排序组合为一种更自然的方式。

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 可能会表现不正确。这也意味着您也无法将它们存储在 std::set 中，因为 std::set 内部以某种排序顺序存储所有内容（通常是平衡二叉搜索树），你可能会得到完全错误的结果。

希望这有帮助！

回复收藏 0 原文

沧笙踏歌 2025-01-03 17:53:37

如果a.first小于b.first，则该对已经较小。没有理由比较第二部分。对隐式地首先按其第一部分排序，就像名称首先按其第一个字母排序一样。 “Apple”位于“Zebra”之前，因为“A”位于“Z”之前，我们根本不将“p”与“e”进行比较。

所以如果 a.first < b.first，我们就完成了。但是，如果没有，我们还没有完成。还有另一种方式 a 可以小于 b。也就是说，如果 b.first < a.first 并非如此，并且 a.second < b.第二个。

类比是“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);
}

我发现这更容易直观地理解，但逻辑是相同的：

If a.first is less than b.first, then the pair is less already. There's no reason to compare the second part. Pairs implicitly sort first by their first part, just as names sort first by their first letter. "Apple" comes before "Zebra" because "A" comes before "Z", we don't compare the "p" to the "e" at all.

So if a.first < b.first, we're done. However, if not, we're not done. There's another way a can be less than b. That's if b.first < a.first is not the case, and a.second < b.second.

The analogy would be "Zebra" and "Zyman". "Z" is not less than "Z", but "e" is less than "y", so again, the first is less than the second.

You will sometimes see it coded this way:

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

I find this easier to understand intuitively, but the logic is the same:

回复收藏 0 原文