Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Custom comparator -- would "<=" save a swap over "<"?

Tags:

c++

Suppose I have a custom multi-criteria comparator, though the multi part probably doesn't matter. To keep it simple, let's say we're sorting arrays consisting of 3 doubles representing coordinates.

I know the go-to comparison operator is "<", but I have this nagging feeling that "<=" might save a swap if all parts are equal. Does the sorter (e.g. std::sort) go, "Hey, if comparator returns false, I'm swapping you!", or is this incorrect assumption? Thanks.

// Compare based on X, then Y, then Z
bool PointComparer(const array<double,3>& a, const array<double,3>& b)
{
    if (a[0] < b[0]) return true;
    if (a[0] > b[0]) return false;

    if (a[1] < b[1]) return true;
    if (a[1] > b[1]) return false;

    return a[2] < b[2];  // If instead was a[2] <= b[2], would it save a swap in equal case?
}
// Later sort a collection of these arrays
like image 505
icy Avatar asked May 10 '18 20:05

icy


1 Answers

You cannot use <= for std::sort() and similar standard algorithms as it does not satisfy Compare concept which requires strict weak ordering and violates this condition:

For all x in S, it is not the case that x < x (irreflexivity).

so using this operator would lead to UB and it meaningless to discuss if it would prevent a swap or not.

like image 153
Slava Avatar answered Sep 22 '22 02:09

Slava