Will std::sort work correctly if I defined a custom compare function for floating number?
c++, floating-point, sorting
Solution
`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.
Problem
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) ```