CODEWITHSUNDEEP
c++sortingfloating-point
chyx
chyx

Reputation: 501

Will std::sort work correctly if I defined a custom compare function for floating number?

For the issue of the floating precision, I defined my custom compare function for floating numbers: 

bool cmp(double a, double b)
{
    if(abs(a - b) <= eps) return false;
    return a < b;
}

Then I call sort on some array of floating numbers. I've heard that some bad compare function will cause the sort to segment fault. I just wondering will cmp work correctly for sort? On one hand, cmp satisfied the associating rule. But on the other hand, cmp(x - eps, x) == false && cmp(x, x + eps) == false doesn't mean cmp(x - eps, x + eps) == false.

I didn't use sort directly on floating numbers because what I want to sort is pair<double, double>. For example:

(1,2), (2,1), (2.000000001, 0)

I'd like to consider 2 and 2.000000001 as the same and expect the result to be:

(1,2), (2.000000001, 0), (2,1)

Upvotes: 3

Views: 994

Answers (3)

MSalters
MSalters

Reputation: 179981

It's possible to define a comparison function for floating point that groups similar values. You do so by rounding:

bool cmp(double a, double b)
{
    const double eps = 0.0001;
    int a_exp;
    double a_mant = frexp(a, &a_exp); // Between 0.5 and 1.0
    a_mant -= modf(a_mant, eps); // Round a_mant to 0.00001
    a = ldexp(a_mant, a_exp); // Round a to 0.00001 * 10^a_exp
    // and the same for b
    int b_exp;
    double b_mant = frexp(b, &b_exp); 
    b_mant -= modf(b_mant, eps);  
    b = ldexp(b_mant, b_exp);
    // Compare rounded results.
    return a < b;
}

Now cmp(a,b)==true implies that a<b, and a==b and a>b both imply cmp(a,b)==false.

Upvotes: -1

Gorpik
Gorpik

Reputation: 11038

std::sort requires a comparer that defines a strict weak ordering. This means, among other things, that the following condition must be met:

  • We define two items, a and b, to be equivalent (a === b) if !cmp(a, b) && !cmp(b, a)
  • Equivalence is transitive: a === b && b === c => a === c

As you already say in your question, your function cmp() does not meet these conditions, so you cannot use your function in std::sort(). Not only the result of the algorithm will be unpredictable, which is bad unless you are actually looking for this unpredictability (cf. randomize): if you have a few values that are very close to each other, such that any of them compare true with some, but false with some others, the algorithm might enter an infinite loop.

So the answer is no, you cannot use your function cmp() in std::sort() unless you want to risk your program freezing.

Upvotes: 6

Kerrek SB
Kerrek SB

Reputation: 477368

Why would you bother to make an approximate less-than comparison? That makes no sense.

Just sort your array strictly by actual values.

Then use your approximate comparison function to determine which of the elements you wish to consider to be equal.

(The equivalent in English would be the infamous "almost better". Think about it.)

Upvotes: 4

Related Questions