stl排序 - 严格的弱排序

Question

为什么STL使用严格弱排序的比较函数？为什么不能进行部分订购？

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).

对于序列中另一个元素之后出现的每个元素,如果f不小于,则对拓扑进行拓扑排序.这是一个比排序更弱的约束.yxyx

证明每个元素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

引用这里给出的答案:

因为在内部,这些算法实现"等于" !(a < b) && !(b < a).

如果您曾经<=实现过less-than运算符,那么上面的内容将返回false a == b.破坏的等式检查几乎会破坏任何算法.

类似地,它们实现"不等于" (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

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