4 ms·
When the STL became part of the standard library ( http://www.stlport.org/resources/StepanovUSA.html http://www.stlport.org/resources/StepanovUSA.html ), there
by maxlybbert 1y ago
When the STL became part of the standard library ( http://www.stlport.org/resources/StepanovUSA.html http://www.stlport.org/resources/StepanovUSA.html ), there was a question of how to handle algorithms that sort containers, or that perform a binary search, or in some other way, need to know whether “a” is less-than, equal-to, or greater-than “b”. The algorithms have to work on primitive types, and user defined types as efficiently as possible. They eventually decided to only require a function for “less-than.” And if “a < b” returns false, and “b < a” also returns false, then “a” and “b” are considered equal.
There are times that doesn’t work, so documentation usually has a footnote that (1) certain algorithms require a partial ordering and not necessarily a total ordering, and (2) to use those algorithms, you must implement less-than, but any other comparison operator is ignored by the algorithm; instead, less-than is used to figure out greater-than and equal-to as needed. This was considered better than requiring programmers to implement a collection of comparison operators, and trusting those programmers to make those operators act consistently with each other (e.g., never say that “a” and “b” are both less-than and greater-than each other).
The spaceship operator seems to address this specific case ( https://open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0515r0.pdf https://open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0515r0... ). According to Herb Sutter (note that his name is on the proposal), “We added the C++20 spaceship operator to the language, but we also applied it throughout the C++ standard library and that made the library specification nearly 20 pages shorter — a net reduction” ( https://herbsutter.com/2020/12/ https://herbsutter.com/2020/12/ ).
- spyrja 1y agoWay back when I actually perused through quite a bit of Stepanov's STL code and stumbled on that very thing, the comparison operator semantics. I remember thinking it very clever of him to approach it that way and it hadn't even crossed my mind at the time that it might lead to some kind of undefined behavior. Thanks for pointing out such an interesting tidbit!
- maxlybbert 1y agoMaybe "doesn't work" is the wrong phrase. Usually, it does what people expect (except that the library ignores any "operator==" or "operator!=", which surprises people who went through the trouble to define them). And depending on what "operator<" does, it's possible for distinct values (a.k.a., not-equal values) to compare "equal." So to avoid confusion, people start using phrases like "equivalent" instead of "equal." But usually there's no real confusion: if you sort a list of strings by length, nobody's surprised when "hello" and "green" compare "equal," even though they have different contents. Everybody realizes that they have equal lengths, not equal contents. The main things I've actually had to watch out for are floating point values that could have not-a-numbers (e.g., https://en.cppreference.com/w/cpp/numeric/math/isunordered.html https://en.cppreference.com/w/cpp/numeric/math/isunordered.h... ), and possibly Unicode strings that aren't normalized ( https://unicode.org/reports/tr15/ https://unicode.org/reports/tr15/ ), but those act weird in all software I'm familiar with. Because people forget about the relevant edge cases.
- spyrja 1y agoYep, exactly. NAN's truly are a great example of just how weird an edge case can get too! #define isNan(X) ((X) != (X))
- metadat 1y agoFor anyone else who forgot this or is unfamiliar with why / how it "works": > #define isNan(X) ((X) != (X)) > Works by exploiting a unique property of NaN (Not a Number) values in the IEEE-754 floating point standard: a NaN is not equal to itself. In other words, if you compare a floating-point variable to itself and the result is false ((X) != (X)(X)!=(X)), then X X is NaN. Fantastic example, thank you @spyrja!