为什么标准库要求严格的弱排序？

Question

为什么 C++ 标准库使用“严格弱排序”的比较函数？为什么不能是部分排序？

Answer 1

偏序

不足以实现某些算法，例如排序算法。由于偏序集合不一定定义集合中所有元素之间的关系，因此如何对偏序内没有顺序关系的两个项目的列表进行排序？

Answer 2

定义（可计算）等价关系

的排序。等价类按严格弱排序进行排序：严格弱排序是对等价类的严格排序。 偏序（不是严格的弱排序）不定义等价关系，因此

任何使用“等效元素”概念的规范对于不是严格弱排序的偏序都是没有意义的。

所有 STL 关联容器在某些时候使用这个概念，因此所有这些规范对于不是严格弱排序的部分排序来说都是没有意义的。 因为偏序（不是严格的弱排序）不一定定义任何严格的排序，所以你不能根据偏序对常识中的“元素进行排序”（你所能做的就是一个具有较弱排序的“拓扑排序”）属性）。

给定

数学集

S
• 部分排序
<
• 超过

  S

x
• 中的值

  S

您可以定义

S

的分区（

S

的每个元素都在

L(x)

、

I(x)

或

G(x)

中）：

L(x) = { y in S | y<x }
I(x) = { y in S | not(y<x) and not(x<y) }
G(x) = { y in S | x<y }

 L(x) : set of elements less than x
 I(x) : set of elements incomparable with x
 G(x) : set of elements greater than x

序列根据 

<

iff

进行排序，对于序列中的每个 x，

L(x)

的元素首先出现在序列中，然后是

I(x)

的元素，然后是

G(x)

的元素。序列是拓扑排序的

iff

对于序列中出现在另一个元素 y 之后的每个元素

x

，

y

不小于

x

。这是一个比排序更弱的约束。证明

L(x)

的每个元素都小于

G(x)

的任何元素是微不足道的。

L(x)

的元素与

I(x)

的元素之间，或者

I(x)

的元素与

G(x)

的元素之间不存在一般关系。但是，如果

<

是严格的弱排序，则

L(x)

的每个元素都小于

I(x)

的任何元素，并且

I(x)

的任何元素都小于

G(x)

的任何元素。如果

<

是严格的弱排序，并且

x<y

则

L(x) U I(x)

的任何元素都小于任何元素

I(y) U G(y)

：任何不大于

x

的元素小于任何不小于

y

的元素。

这不一定适用于部分排序。

Answer 3

here

给出的答案：

因为在内部，这些算法将“等于”实现为

!(a < b) && !(b < a)

。

如果你使用

<=

来实现小于运算符，那么上面的 当

a == b

时将返回 false。不完善的平等检查将会搞砸 几乎任何算法。同样，他们将“不等于”实现为

(a < b) || (b < a)

，再一次，如果您使用

<

实现了

<=

运算符，那么它 当它们彼此相等时将返回 true，而实际上它们 不相等。因此相等性检查在两个方向上都被破坏了。将库限制为小于运算符的要点是 所有逻辑运算符都可以用它来实现：

<(a, b)
• ：

  (a < b)

<=(a, b)
• ：

  !(b < a)

==(a, b)
• ：

  !(a < b) && !(b < a)

!=(a, b)
• ：

  (a < b) || (b < a)

>(a, b)
• ：

  (b < a)

>=(a, b)
• ：

  !(a < b)

只要您提供的操作员满足以下条件，此操作就有效 严格的弱排序。标准

<=

和

>=

运算符则不然。

Answer 4

算法

中的哪些函数/数据类型需要排序并且可以使用部分排序？