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

顺序是按照 < 森林论坛 每 x 在序列的要素 L(x) 首先出现的顺序，随后通过的元素 I(x), ，随后通过的元素 G(x).

一序列是拓扑排 森林论坛 对于每一个元素 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

引述给出的答案 在这里，:

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

如果你使用 <= 实施低于操作者，然后在上面 将返回虚假的时候 a == b.一个破碎的平等检查将搞砸了 几乎所有算法。

同样，他们实行"不等于"为 (a < b) || (b < a) 再次，如果你执行 < 操作者使用 <=, 然后它 将返回的真正当他们彼此相等的，而事实上他们 不是相等的。所以平等检查被破坏两个方向。

整点的限制图书馆的一个不算是 所有的逻辑运营商可以实现的条款：

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

可以不执行与部分排序二进制搜索。你不能建立一个有偏序二叉搜索树。哪些功能/数据类型从的算法的需要订货，可与部分排序工作？