C++

Forum

 
What is a strict weak ordering?

JUANDENT (411)
a total ordering means for all a,b in Container, one of the following is true:

a < b
a == b
a > b

so, all elements are comparable (this is the total part). But what is the meaning of weak ordering? And what is meant by strict weak ordering??

I have googled but it's not clear to me.

Please shed some light...
kigar64551 (814)
Last edited on
mbozzi (3932)
For the STL's purposes, a strict weak order is a relation that answers the question "is x ordered-before y?".

A strict weak order is a slightly restricted version of a strict partial order.

For a strict partial order:
- strict means that x is never ordered-before x. (x is not less than x)
- partial means x and y might be tied: in that case, neither x nor y may be ordered-before the other.

A strict weak order has the additional restriction that if x is tied with y, and y is tied with z, x is also tied with z.
Last edited on
helios (17574)
More succinctly, a strict weak ordering is equivalent to < over the integers.

For all x in N, !(x < x).
There exist x, y in N such that !(x < y) && !(y < x).
For all x, y, z in N, (x < y && y < z) => x < z.
JUANDENT (411)
would this be different for < over the floating point numbers??
JUANDENT (411)
Concerning this statement:

if x is tied with y, and y is tied with z, x is also tied with z.

doesn't it mean that if x is tied with y then x < y == false and y < x == false
so in that case x must be equal to y: x == y must be true??

regarding partial, does that mean that there exist x,y in some SET such that:
x and y are tied and therefore both of these are false: x < y, y < x ?
being tied implies x and y are equal??


can you show by example an ordering that is not strict weak ordering? or that is strict partial ordering?


helios: what is an example of integers x,y such that !(x < y) && !(y < x).
doesn't that imply x == y?

Last edited on
helios (17574)
would this be different for < over the floating point numbers??
For floats specifically, yes, it would be different, because the float domain has unsortable values. If you meant to ask about reals, then no, it would be the same. I mentioned the integers because they're more relevant in CS.

what is an example of integers x,y such that !(x < y) && !(y < x).
doesn't that imply x == y?
Yes, but a weak ordering does not consider a symmetric relation.

doesn't it mean that if x is tied with y then x < y == false and y < x == false
so in that case x must be equal to y: x == y must be true??

regarding partial, does that mean that there exist x,y in some SET such that:
x and y are tied and therefore both of these are false: x < y, y < x ?
being tied implies x and y are equal??
No, it means they're incomparable. They might be exactly the same value or not, it depends on the type being considered. It is possible to construct types where incomparable values are not equal. For example,
1
2
3
4
5
6
7
8
9
 
struct A{
    int x, y;
    bool operator<(const A &other) const{
        return this->x < other.x;
    }
    bool operator=(const A &other) const{
        return this->x == other.x && this->y == other.y;
    }
};
You might want to define something like this because you need sorting to be specifically decoupled from equality.
Another possibility is that the type is a representation of some other type, and you want to sort by the represented type, but compare equality of the representation.
!("sqrt(1)" < "1") && !("1" < "sqrt(1)")
!("sqrt(1)" == "1")
Still another possibility is that the < relation doesn't compare the values themselves, but how they're related to each other. Suppose you're comparing the nodes of a tree and x < y is true if x is a parent or ancestor of y. There may be nodes on the tree that are unrelated but which are not the same node.

can you show by example an ordering that is not strict weak ordering? or that is strict partial ordering?
A topological sort of a directed acyclic graph requires defining an ordering where incomparability is intransitive.
If you have five software packages with the following dependency graph:
1
2
3
4
 
A <---- B <------ E
^                 |
|                 |
+--- C <---- D <--+

C is incomparable with B and B is incomparable with D, but C is not incomparable with D. That is, [B and C] and [B and D] can be installed in any other with respect to each other, but D must be installed after C.
Last edited on
JUANDENT (411)

For floats specifically, yes, it would be different, because the float domain has unsortable values.


Can you give me an example of 2 such floats?

helios (17574)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#include <iostream>
#include <cmath>

const char *p(bool b){
    return b ? "true" : "false";
}

int main(){
    auto x = 1.0;
    auto y = std::nan("foo");
    std::cout <<
        "1.0 <  NaN: " << p(x <  y) << "\n"
        "1.0 >  NaN: " << p(x >  y) << "\n"
        "1.0 == NaN: " << p(x == y) << "\n"
        "NaN <  NaN: " << p(y <  y) << "\n"
        "NaN >  NaN: " << p(y >  y) << "\n"
        "NaN == NaN: " << p(y == y) << "\n"
    ;
    return 0;
}
JUANDENT (411)
Thanks Helios!!

Topic archived. No new replies allowed.