stl ordering - strict weak ordering

问题:

Why does STL work with a comparison function that is strict weak ordering? Why can't it be partial ordering?

回答1:

A partial order would not be sufficient to implement some algorithms, such as a sorting algorithm. Since a partially ordered set does not necessarily define a relationship between all elements of the set, how would you sort a list of two items that do not have an order relationship within the partial order?

回答2:

Simply, a strict weak ordering is defined as an ordering that defines a (computable) equivalence relation. The equivalence classes are ordered by the strict weak ordering: a strict weak ordering is a strict ordering on equivalence classes.

A partial ordering (that is not a strict weak ordering) does not define an equivalence relation, so any specification using the concept of "equivalent elements" is meaningless with a partial ordering that is not a strict weak ordering. All STL associative containers use this concept at some point, so all these specifications are meaningless with a partial ordering that is not a strict weak ordering.

Because a partial ordering (that is not a strict weak ordering) does not necessarily define any strict ordering, you cannot "sort elements" in the common sense according to partial ordering (all you can do is a "topological sort" which has weaker properties).

Given

• a mathematical set S
• a partial ordering < over S
• a value x in S

you can define a partition of S (every element of S is either in L(x), I(x) or 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

A sequence is sorted according to < iff for every x in the sequence, elements of L(x) appear first in the sequence, followed by elements of I(x), followed by elements of 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.

回答3:

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.

回答4:

You cannot perform binary search with partial ordering. You cannot create a binary search tree with partial ordering. What functions/datatypes from algorithm need ordering and can work with partial ordering?