c++algorithmlanguage-lawyerstrict-weak-ordering

Does greater operator ">" satisfy strict weak ordering?

Definition:

Let < be a binary relation where a < b means "a is less than b".

Let > be a binary relation where a > b means "a is greater than b".

So, we assume < and > have meanings we usually use in a daily life. Though, in some programming languages (e.g. C++), we can overload them to give them different definitions, hereafter we don't think about that.

Context:

As far I read mathematical definition of strict weak ordering (e.g. Wikipedia), I think both < and > satify it. However, all examples I saw in many websites refer only to <. There is even a website which says

what they roughly mean is that a Strict Weak Ordering has to behave the way that "less than" behaves: if a is less than b then b is not less than a, if a is less than b and b is less than c then a is less than c, and so on.


Also, in N4140 (C++14 International Standard), strict weak ordering is defines as

(§25.4-4) If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations

where comp is defined as

(§25.4-2) Compare is a function object type (20.9). The return value of the function call operation applied to an object of type Compare, when contextually converted to bool (Clause 4), yields true if the first argument of the call is less than the second, and false otherwise. Compare comp is used throughout for algorithms assuming an ordering relation.

Question:

Does ">" satisfy strict weak ordering? I expect so, but have no confidence.

Solution

  • Does greater operator “>” satisfy strict weak ordering?

    The mathematical strict greater than relation is a strict weak ordering.

    As for the operator in C++ langauge: For all integers types: Yes. In general: No, but in most cases yes. Same applies to strict less than operator.

    As for the confusing quote, "is less than" in that context intends to convey that means that the the end result of the sort operation is a non-decreasing sequence i.e. objects are "less" or equal to objects after them. If std::greater is used as comparison object, then greater values are "lesser" in order.

    This may be confusing, but is not intended to exclude strict greater than operator.

    what is the case where > doesn't satisfy strict weak ordering?

    Some examples: