PartialOrdering, StrictWeakOrdering, TotalOrdering

2019-02-17 23:58发布

问题:

[SGI official document]

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.

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.Is partial ordering implicitly define a equivalence?

2.What about strict weak ordering and total ordering?

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

回答1:

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.

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.

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