21

为什么 STL 可以使用严格弱排序的比较函数？为什么不能是偏序？

4

4 回答 4

19

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

于 2009-08-18T11:25:32.390 回答
12

简单地说，严格的弱排序被定义为定义（可计算的）等价关系的排序。等价类按严格弱排序排序：严格弱排序是对等价类的严格排序。

偏序（不是严格的弱序）没有定义等价关系，因此任何使用“等价元素”概念的规范对于不是严格弱序的偏序都是没有意义的。所有 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)。

A sequence is topologically sorted iff for every element y that appears after another element x in the sequence, y is not less than x. It is a weaker constraint than being sorted.

It is trivial to prove that every element of L(x) is less than any element of G(x). There is no general relation between elements of L(x) and elements of I(x), or between elements of I(x) and elements of G(x). However, if < is a strict weak ordering, than every element of L(x) is less than any element of I(x), and than any element of I(x) is less than any element of G(x).

If < is a strict weak ordering, and x<y then any element of L(x) U I(x) is less then any element I(y) U G(y): any element not greater than x is less than any element not less that y. This does not necessarily hold for a partial ordering.

于 2013-05-22T14:47:30.517 回答
7

Quoting the answer given here:

Because internally, these algorithms implement "is equal to" as !(a < b) && !(b < a).

If you used <= to implement the less-than operator, then the above would return false when a == b. A broken equality check will screw up nearly any algorithm.

Similarly, they implement "is not equal to" as (a < b) || (b < a) , and once again, if you implemented the < operator using <=, then it will return true when they are equal to each other, when in fact they are not equal. So the equality check is broken in both directions.

The whole point of limiting the library to a less-than operator is that all of the logical operators can be implemented in terms of it:

  • <(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)

This works as long as your provided operator meets the conditions of a strict weak ordering. The standard <= and >= operators do not.

于 2016-03-03T13:44:53.200 回答
5

您不能使用偏序执行二进制搜索。您不能创建具有偏序的二叉搜索树。算法中的哪些函数/数据类型需要排序并且可以使用部分排序？

于 2009-08-18T14:36:53.000 回答