PartialOrdering，StrictWeakOrdering，TotalOrdering，应用程序的主要区别是什么 [英] PartialOrdering, StrictWeakOrdering, TotalOrdering, what's the main difference in application

问题描述

[SGI官方文档]

由于不自反性和可传递性，运算符<总是满意 偏序的定义.严格弱的定义 订购更严格，总订购的定义是 更严格.

Because of irreflexivity and transitivity, operator< always satisfies the definition of a partial ordering. The definition of a strict weak ordering is stricter, and the definition of a total ordering is stricter still.

我还阅读了文档中严格弱排序的定义: StrictWeakOrdering

And I also read the definition of strict weak ordering in the document: StrictWeakOrdering

前三个公理，不自反性，反对称性和可传递性， 是部分排序的定义；等价的及物性 严格的弱排序的定义是必需的.合计 有序是满足更强条件的一种:等价 必须与相等相同.

The first three axioms, irreflexivity, antisymmetry, and transitivity, are the definition of a partial ordering; transitivity of equivalence is required by the definition of a strict weak ordering. A total ordering is one that satisfies an even stronger condition: equivalence must be the same as equality.

我对这些定义不太确定.一些主要问题:

I am not quite sure about these definition. Some main questions:

1. 偏序是否隐式定义了等价物?

1.Is partial ordering implicitly define a equivalence?

2.严格弱排序和总排序怎么办?

2.What about strict weak ordering and total ordering?

3.STL在排序算法中要求严格的弱排序，为什么不执行部分排序或全部排序? 对于这个问题，我已经阅读了一些教科书，这些教科书通过证明该规则满足三个公理来证明该比较规则是有效的:不反身性，反对称性，可传递性(这是部分排序的定义)，并且文档中提到运算符<总是满足这个定义，所以为什么我们不能只使用部分排序或等效地使用运算符来比较对象

3.STL require a strict weak ordering in sort algorithms, why isn't partial ordering or total ordering? For this question, I've read some textbooks that prove a valid comparing rules by proving the rule satisfy three axioms: irreflexivity, antisymmetry, transitivity which is the definition for partial ordering, and the document refer that operator< always satisfies this definition, So why can't we just compare objects using partial ordering, or equivalently, using operator

推荐答案

部分排序实质上是<=.如果同时使用a <= b和b <= a，则可以说a等同于b.但是a <= b和b <= a两者都是不可比拟的，这也是有可能的.结果，您不能对具有部分排序关系的集合施加总排序(如std::sort那样)-充其量您可以进行拓扑排序.您也无法得出等价关系-再次，可能有些元素是无法比拟的.

Partial ordering is, essentially, <=. If both a <= b and b <= a then you may say that a is equivalent to b. But it's also possible that neither a <= b nor b <= a - the two elements are incomparable. As a result, you cannot impose a total order (like std::sort would need to) on a set with partial ordering relation - at best you can do a topological sort. Nor can you derive an equivalence relation - again, there may be elements that are incomparable.

严格的弱排序类似于<.不允许同时具有a < b和b < a，并且如果a < b和b < a都不存在，则只能发音a和b等价物.

Strict weak ordering is like <. It doesn't allow having both a < b and b < a, and if neither a < b nor b < a, you can just pronounce a and b equivalent.

总排序只是严格的弱排序，其中两个元素仅当且仅当它们相等时才等效(这仅在您具有除小于谓词以外的相等比较谓词且没有C ++标准库算法的情况下才有意义.同时使用这两者，因此在此情况下，这个问题基本上没有解决.

Total ordering is simply strict weak ordering where two elements are equivalent if and only if they are equal (which is only meaningful if you have an equality comparison predicate in addition to less-than predicate, and there is no C++ standard library algorithm that uses both at the same time, so the issue is largely moot in this context).

这篇关于PartialOrdering，StrictWeakOrdering，TotalOrdering，应用程序的主要区别是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！