5

根据cppreference：

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

翻译成这样的东西：

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

我的问题是，为什么它如此不直观？其背后的原因是什么？有没有这样的推理导致正确答案的例子？

我认为实现将只是：

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

3 回答 3

12

这种比较称为字典顺序，是将两种不同的顺序组合为一个的更自然的方法之一。

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内部以某种排序顺序存储所有内容（通常是平衡的二叉搜索树），您可能会得到完全错误的结果。

希望这可以帮助！

于 2012-01-19T23:04:09.450 回答
6

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

我觉得这更容易直观理解，但逻辑是一样的：

于 2012-01-19T23:03:55.357 回答
4

直觉在旁​​观者的眼中。实际上，我自己觉得它很直观。

它就像您在比较其他序列时所做的那样。例如，您会说字符串"az"在 之前"ba"，对吗？但是你没有'a' < 'b' && 'z' < 'a'！同样的推理也适用于对。它不仅更直观，而且还保留了这种关系的所有理想属性。

于 2012-01-19T23:04:43.867 回答