Why does the standard library require a strict weak ordering?

Question

Why does C++ standard library work with a comparison function that is strict weak ordering? Why can't it be partial ordering?

Telford

Couldn't you clarify of show sample what do you mean? – Megasporophyll

Answer 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?

Kitchen

"partially ordered set does not necessarily define a relationship between all elements of the set" strict weak ordering is no better, it does not always make an element less than or greater than another. – Nobleminded

@Nobleminded elements comparing equivalent is not the same as elements being incomparable – Mussman

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

Nobleminded

So actually strict weak ordering do define a equivalence relationship implicitly? Say if I(x) < x is false and x < I(x) is false, will this yield a result of x == I(x) ? – Wrongdoer

@zoujyjs I(x) is a set (a part of S); by I(x) < x do you mean: for each y which is an element of I(x), y < x? If so not(x < E) and not(E < x) (where x is an element of S and E is a part of S) does not imply E = {x}. – Nobleminded

The first paragraph could use some work. I don't think the word "ordering" has a generally agreed on definition, so perhaps instead say "a strict partial ordering"... but only if that's what you really mean (I'm actually not sure). Also it's not clear at this point how it defines an equivalence relation. And I don't think the "(computable)" makes any sense here. So, suggested rewrite of first sentence: "Simply, a strict weak ordering can be defined as a strict partial ordering < in which the relation (not(a<b) and not(b<a)) is an equivalence relation". If that's what you mean. – Beadle

Hum... my answer had serious issues with the wording! I am ashamed now. The answer NEEDED editing, indeed. – Nobleminded

"And I don't think the "(computable)" makes any sense here." In the context of the STL, a relation is not just a mathematical relation. A relation that is mathematically well defined but that you cannot compute is useless. In the context of the STL, a relation is a C++ function (or functor) returning a boolean and a mathematical relation, and the C++ function must return a value (not loop, not call exit) and the returned value must be true iff the relation holds. – Nobleminded

Looks like my edit got accepted after all. I've deleted my previous comment in this thread, which contained the laundry list. – Beadle

Regarding that first sentence: since I don't know what you mean by "ordering" (an arbitrary relation? a strict partial ordering? what?) it's hard for me to nail down what this sentence is saying. But one part of it that looks clearly wrong to me is that it's saying a "strict weak order" must be computable. That's just not true; "strict weak ordering" has a precise definition (see wikipedia) that doesn't require computability. Your sentence is roughly of the form "an A is a (computable) B"; I think you probably want to be saying either "an A is a B" or "a (computable) A is a (computable) B". – Beadle

To be precise, I suggest either "Simply, a strict weak ordering can be defined as a strict partial ordering < in which the relation (not(a<b) and not(b<a)) is an equivalence relation" or "Simply, a (computable) strict weak ordering can be defined as a (computable) strict partial ordering < in which the relation (not(a<b) and not(b<a)) is an equivalence relation". If you change it to one of these, it will then be a precise statement and then I can move on to thinking about whether it's true or not (i.e. whether it agrees with the usual definition of SWO). At this moment I'm not sure! – Beadle

A partial ordering (that is not a strict weak ordering) does not necessarily define any strict ordering. Agreed. But why it has to be partial ordering? Why can't standards use total ordering? – Rusty

@DonHatch In the context of C++ template code, of course. It has to be computable. It applies to C++ objects, not abstract entities. We aren't discussing pure abstract math here. How pure abstract math relates to C and C++ is often quite obscure, as specifications are extremely poorly written (nobody in either committee seems to have any grasp on what a PL specification is). – Nobleminded

@SouravKannanthaB What is a "total ordering" and how is it different from a partial ordering? How would that difference make a difference for set, map? – Nobleminded

@Nobleminded "It applies to C++ objects, not abstract entities." This actually isn't true at all-- strict weak ordering is in fact a standard mathematical term which doesn't imply computability: see en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings It doesn't look to me like the "(computable)" adds anything to your answer, so how about just removing it, to avoid this derailment? – Beadle

@DonHatch Your ref doesn't say anything about the STL. My answer is about the STL. The derailment is insisting that computability isn't central to the issue. – Nobleminded

"Your ref doesn't say anything about the STL." Right, that's because the STL documentation refers to the standard mathematical definition of SWO (same as in wikipedia, and doesn't include computability), not vice versa. Your first paragraph claims that SWO means something else, so it's either simply incorrect or you've invented your own non-standard definition of SWO; either way it's unnecessarily confusing. This could be fixed by simply removing the "(computable)" and I don't see any downside since that word still doesn't look to me like it adds anything to your answer. -1 for now, I guess. – Beadle

@DonHatch The whole point of the STL is that is uses functors. So of course the relation must be computable. How would you even construct anything otherwise? I can rewrite my answer (and probably will) but I can't remove the most central element, that SWO is the thing being measured about objects in that part of the STL. – Nobleminded

Hi @Nobleminded -- it's clear that we are having trouble communicating with each other, but I'm not sure how to fix it :-) I appreciate you engaging, and I'll try some more. Sure, in order to use these tools, the relation being computed must be computable, I don't disagree with that. The problem is just that your first sentence makes a stronger (and false!) statement: "a strict weak ordering is defined as an ordering that defines a (computable) equivalence relation. " This implies that every SWO is computable, which just isn't true, and doesn't need to be said in order to make your point! – Beadle

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

Epigenesis

Answer 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?

Gasperoni