1

Since comparing floats is evil then if I have a container of floats and I sort it using some standard library sorting algorithm like std::sort then how does the algorithm sort them?

std::vector<float> vf{2.4f, 1.05f, 1.05f, 2.39f};
std::sort( vf.begin(), vf.end() );

  • So does the algorithm compare 1.05f and 1.05f?

  • Does it internally uses something like: std::fabs( 1.05f - 1.05f ) < 0.1;?

  • Does this apply too to containers of doubles? Thank you!

Itachi Uchiwa
  • 3,044
  • 12
  • 26
  • 4
    Looks like misunderstanding what is problem when comparing floats. Comparing floating points by less or grater operator is fine. Comparing floating points to be equal or not equal is evil. Please read: https://stackoverflow.com/q/588004/1387438 – Marek R Sep 17 '21 at 10:33
  • I recommend printing this pdf document and putting it on your bedside table: [What every programmer should know about floating-point arithmetic (pdf)](https://www.itu.dk/~sestoft/bachelor/IEEE754_article.pdf) – Stef Sep 17 '21 at 10:44
  • if it would use `std::fabs( 1.05f - 1.05f ) < 0.1;` strange things would happen. For example `0.4` is not smaller than `0.5`, `0.5` is not smaller than `0.6` .... `99.9` is not smaller than `100.0` and by transitivity `0.4` is not smaller than `100.0`. – 463035818_is_not_an_ai Sep 17 '21 at 10:51

2 Answers2

4

So does the algorithm compare 1.05f and 1.05f?

Yes

Does it internally uses something like: std::fabs( 1.05f - 1.05f ) < 0.1;?

No, it uses operator <, e.g. 1.05f < 1.05f. It doesn't ever need to compare for equality, so the comparison using epsilon value is not needed.

Does this apply too to containers of doubles?

Yes, it applies to containers of any type (unless you provide your own comparison function to std::sort)

Yksisarvinen
  • 18,008
  • 2
  • 24
  • 52
  • 4
    More specifically, it uses whatever [std::greater](https://en.cppreference.com/w/cpp/utility/functional/greater) or other functor uses in its implementation. – Kaihaku Sep 17 '21 at 10:38
  • One last thing off topic: We should not compare doubles too for equality? if(3.14 == 3)? – Itachi Uchiwa Sep 17 '21 at 10:39
  • 2
    @ItachiUchiwa Comparison using `==` with any floating point type is likely to fail. `0.3 == 0.3` will be `true`, but `0.1 * 3 == 0.3` will probably be `false`. – Yksisarvinen Sep 17 '21 at 10:44
  • 2
    @Kaihaku - No, it doesn't. `std::sort` is *literally* specified to use `<`. There's a fair few implementations that do not bother with indirection via `std::less`, and it can [affect behavior](https://stackoverflow.com/q/48878629/817643). – StoryTeller - Unslander Monica Sep 17 '21 at 11:03
  • @StoryTeller-UnslanderMonica that's just one specialization for cases where you don't specify the comparator, which has very little use unless you use nothing but types with default `<` operator being clear cut and don't want an order different from what `std::sort` results in by default. – Kaihaku Sep 17 '21 at 11:16
  • @Kaihaku - That's not a specialization, that's an overload. And what does any of this have to do with your blanket statement? – StoryTeller - Unslander Monica Sep 17 '21 at 11:53
  • @StoryTeller-UnslanderMonica I don't really know what's the point of arguing implementation details on this matter but there's nothing preventing that overload from specifying a default comparator instead of `operator<` explicitly, which you know, that's what for example gcc does... See [here](https://github.com/gcc-mirror/gcc/blob/d9375e490072d1aae73a93949aa158fcd2a27018/libstdc%2B%2B-v3/include/bits/stl_algo.h#L4795-L4822) and [here](https://github.com/gcc-mirror/gcc/blob/16e2427f50c208dfe07d07f18009969502c25dc8/libstdc%2B%2B-v3/include/bits/predefined_ops.h#L33-L44). – Kaihaku Sep 17 '21 at 12:04
  • @Kaihaku - The public overload doesn't specify any default. And the internal one is given one that applies to iterators, hence the `*it1 < *it`. Which is *exactly* doing direct comparison on the elements with `<`. And now I indeed see there is no point discussing this with you. – StoryTeller - Unslander Monica Sep 17 '21 at 12:10
  • @StoryTeller-UnslanderMonica Its pointless only because you're missing the fact that implementation of `__gnu_cxx::__ops::__iter_less_iter` could be modified without modifying `std::sort` code, as it is not using `<` operator directly. I don't know what you're trying to imply, but no, writing out whole sorting algorithm in `main` is not the same as calling `std::sort`, I hope I don't need to explain why. So I went ahead and proven that my blanked statement is objectively correct for at least one implementation, what now? – Kaihaku Sep 17 '21 at 12:15
3

Since comparing floats is evil…

That is a myth and is false. Related to it is the myth that floating-point numbers approximate real numbers.

<, <=, >, and >= work fine for sorting numbers, and == and != also correctly compare whether two numbers are equal. <, <=, >, and >= will not serve when sorting data containing NaNs (the “Not a Number” datum).

Per the IEEE 754 Standard for Floating-Point Arithmetic and other common specifications of floating-point formats, any floating-point representation ±F•be represents one number exactly. Even +∞ and −∞ are considered to be exact. It is the operations in floating-point arithmetic, not the numbers, that are specified to approximate real-number arithmetic. When a computational operation is performed, its result is the real-number results rounded to the nearest representable number according to a chosen rounding rule, except that operations with domain errors may produce a NaN. (Round-to-nearest-ties-to-even is the most common rule, and there are several others.)

Thus, when you add or subtract numbers, multiply or divide numbers, take square roots, or convert numbers from one base to another (such as decimal character input to internal floating-point format), there may be a rounding error.

Some operations have no error. Comparison operations have no error. <, <=, >, >=, ==, and != always produce the true mathematical result, true or false, with no error. And therefore they may be used for sorting numbers. (With NaNs, they always produce false, because a NaN is never less than, equal to, or greater than a number, nor is a NaN less than, equal to, or greater than a NaN. So false is the correct result, but it means these comparisons are not useful for sorting with NaNs.)

Understanding this distinction, that numbers are exact and operations may approximate, is essential for analyzing, designing, and proving algorithms involving floating-point arithmetic.

Of course, it may happen that in an array of numbers, the numbers contain errors from earlier operations: They differ from the numbers that would have been obtained by using real-number arithmetic. In this case, the numbers will be sorted into order based on their actual computed values, not on the values you would ideally like them to have. This is not a barrier to std::sort correctly sorting the numbers.

To sort data including NaNs, you need a total order predicate that reports whether one datum is earlier than another in the desired sort order, such as one that reports a NaN is later than any non-NaN. IEEE-754 defines a total order predicate, but I cannot speak to its availability in C++. (std::less does not seem to provide it, based on a quick test I tried.)

Eric Postpischil
  • 195,579
  • 13
  • 168
  • 312