Comparison is not simple, but it can be simpler
summary
The standard’s algorithms require a strict weak order and passing general floating‑point values to std::sort is undefined: examples show five‑element inputs with NaNs producing wildly different sorted partitions and binary_search failures, and memoization over 1/x breaks because +0/−0 and many distinct NaNs behave inconsistently. The uploader supplies code and slides on GitHub that implement IEEE’s total order function and three comparator kinds (partial, weak, total), which fix sorting and memoization; a proposal (N4367) pushes ternary comparators into the library.
AI-written summary · about
chapters (22)
- 0:00Intro
- 0:16What is comparison?
- 1:11What is an equivalence relation?
- 2:18What is an order relation?
- 4:39What comparison orders are needed?
- 6:37How is sorting with NaN?
- 7:54How is sorting with signed zero?
- 10:25How is memoization with NaN?
- 13:47Is floating point the only problem?
- 16:05What is the real problem?
- 16:51Can it get worse?
- 19:59Write boolean comparison functions.
- 22:41How do we handle floating point?
- 23:27Respect IEEE 754 totalOrder.
- 25:06Check relationship with operators.
- 25:45Take advantage of common cases.
- 27:01How do we handle Zip+4 codes?
- 30:05How do we compare composite types?
- 33:10What can the standard do?
- 37:27Can we make coding easier?
- 39:24What is the path forward?
- 41:22Questions?
related talks
52m“Regular Types and Why Do I Care ?”
58mUsing C++20's Three-way Comparison ＜=＞
27m“A Little Order: Delving into the STL sorting algorithms”
01h 00mCustomizing the Standard Containers
58mPortable floating-point calculations
47mHow the JVM Optimizes Generic Code - A Deep Dive
01h 03mstd::midpoint? How Hard Could it Be?
07mISO/IEC 14882