Comparisons in C++20
brevzin.github.io
brevzin.github.io
The reality is that most programmers are not experts but they exist on C++ projects. People will try “simple” things like hacking up a less-than operator, and when it seems to “work”, they move on (leaving a code time bomb behind).
The C++ compiler needs to provide robust compile-time and run-time checks to tell programmers that things are wrong, like: “your operator does not meet the requirements of the sort algorithm”.
Contrast the latest 20-page description of std::whatever_the_heck to, say, Python sorting, which offers "key=..." because the overwhelmingly common case is to simply state a single field on which to base object ordering!!!
Python 3 also removed the “everything is comparable” misfeature of P2, providing way lower incentive to implement ordering: if your type is not orderable, a user knows to go with key functions.
def __lt__(self, other):
return self.a < other.a and self.b < other.b and self.c < other.c
def __cmp__(self, other):
v = cmp(self.a, other.a)
if v != 0:
return v
v = cmp(self.b, other.b)
if v != 0:
return v
v = cmp(self.c, other.c)
if v != 0:
return v
return 0
impl Ord for Thing {
fn cmp(&self, other: &Self) -> Ordering {
self.a.cmp(&self.a)
.then(self.b.cmp(&other.b))
.then(self.c.cmp(&other.c))
}
}All those functions implement the same comparison, the first is simply not including the similarly trivial implementation for eq:
def __eq__(self, other):
return self.a == other.a and self.b == other.b and self.c == other.c
Every word here makes sense but the objection makes none. What are you trying to say exactly?
So you want eq, seperate from cmp. Then you still need a way to define ordering, so either write them all for weird cases, or just pick one and have total_ordering do the legwork.
Removing `__cmp__` was a step backwards IMHO.
This again goes back to what masklinn said: a total ordering across all objects in python is a misfeature. The idea that `object() < 13 < "hello world" < 3+2j < [(frozenset(), frozenset())] < {type: int}` should evaluate to anything but a TypeError is horrifying!
And once you make that decision, if an object implements cmp, it must implement eq (because the safe thing should be the default, and allowing people to implement cmp in isolation lets them shoot themselves in the foot). And at that point, cmp is more work to write than le or gt, so instead just implement eq, and then if you want it, le or gt + total_ordering, or if you need weird things implement each method individually.
In practice, I've also found it much easier to reason about eq or le than cmp. People like to be tricky with cmp, and even when they don't, returning -1 or 1 is less explicit than just returning True or False.
At least it evaluates to False.
That's the flaw which cpp avoids, although it remains to be seen if implementing complex spaceships is worth it.
Or I guess, python is now in the pre-cpp20 state, but was never in the post-cpp20 state, so it didn't revert. Python's cmp was broken.
I didn't say that Python was in post-cpp20. Maybe you wanted to comment on my previous comment.
Which is the statement I originally took issue with.
Hard to do without breaking backward compatibility, which is among the main reasons why we still write C++.
It’s done in C#. CS0216 forces you to implement operators in sets, e.g. can’t implement `==` without also implementing `!=` it won’t build otherwise: https://docs.microsoft.com/en-us/dotnet/csharp/misc/cs0216
And these warnings are printed for compatibility with containers: https://docs.microsoft.com/en-us/dotnet/csharp/misc/cs0660 https://docs.microsoft.com/en-us/dotnet/csharp/misc/cs0661
So… that you can provide incoherent implementations of == and != instead of the system just generating one based on the other?
Even when they return bool, in some cases both greater and less must return false. Example: https://en.wikipedia.org/wiki/NaN#Comparison_with_NaN
I think it’s the other way. Providing one based on the other is a pointless footgun.
The experience doesn’t end when you’ve made machine code from your source. Developers debug stuff. Developers support their products, sometimes analyzing crash dumps. The more magic is used in the compiler, the harder it is to debug and support software.
Sometimes that’s justified, e.g. in C# there’s substantial amount of compiler magic for generators and async functions. But these 2 features save substantial amount of code complexity.
Implementing != from == and > from < only provides minimal profit. The manual implementation is a single line method.
Another reason, C# is different language than Rust or Python. It has awesome support for OOP and runtime reflection. What should happen if you use reflection to get op_Inequality for a class where only == is defined? What should happen if you define == in a base class and != in a derived one?
> Hard to do without breaking backward compatibility, which is among the main reasons why we still write C++.
Although the language specification may need to preserve backwards compatibility, compilers can offer strictness warnings that go beyond that (e.g. -Wstrict). And the standards have deprecated and removed things as well. It’s not a straightjacket.
Making this a warning would probably break too much existing code.
In the case of the standard library, the whole library is being hoisted to use <=> in c++ 20. Old code will still work with the latest library of course.
Maybe, but I think it’s hard to do in practice. Many C++ libraries are header only because templates, i.e. old and new stuff is mixed really well.
Differentiating warnings is possible with #pragma but they aren’t portable across compilers.
I know this doesn't work for everyone and we can't even do it with everything. But it helps a lot.
MSVC does that in debug mode - it will assert if you use an invalid comparator for e.g. map / set. No reason it couldn't be further improved, or a clang-tidy check written for that.
Some things are actually more productive in MS land for security conscious coding. A nice side effect from all those Windows 9X exploits.
I wanted a map from tile position to something else. I found that I had to implement operator<, because std::map uses operator<. That's an issue, because:
1. I didn't want to implement every single possible comparison operator just to put vectors in an array, but also didn't want to arbitrarily make `foo < bar` legal but `foo > bar` illegal.
2. What does it even mean for one vector to be "bigger than" another vector? For vector math purposes, I'd maybe expect operator< to compare magnitudes, but that would be absolutely terrible for std::map. Not everything has an unambiguous concept of "smaller than".
In the end I just made a std::map<std::pair<int, int>> and added an implicit conversion from Vector2<T> to std::pair<T, T>.
I'll keep hash_map in mind though, and maybe do some performance testing to see which is actually faster.
Note: when I say "incredibly slow", it is relative to what is possible to achieve in C++ - it will still roll over many other languages's map implementations.
[1] - https://chromium.googlesource.com/chromium/src/+/master/base...
C# is slightly different: all of the algorithms take an IComparison, which implements the spaceship operator in another class (you can implement the related IComparer in your actual class and it all works via the magic of reflection. This isn't too bad since the reflection only occurs in the constructor.). Comparison operators are basically never used in the standard library and people rarely implement them.
When defaulting the spaceship operator, the same happens for C++ (by comparing members). In this special case, the equality operator is also effectively defaulted, so as described in the article
struct A {
…
auto operator<=>(A const& rhs) const = default;
};
Why do we need a primary == operator if we have strong_ordering::equal, weak_ordering::equivalent, and partial_ordering::equivalent? Couldn't the behavior of == and != be inferred from the <=> definition?
I guess I'm asking why a == b can't be rewritten as (a <=> b) == 0.
Weak orderings are defined as orders that can't distinguish between all members, which is why it is called "equivalent" instead of "equal".
I get that. This wasn't my question.
I want to know why I need to define operator== when reasonable behavior can be inferred from whether or not operator<=> returns strong_ordering::equal (or weak_ordering::equivalent -- the standards committee can decide if this is reasonable -- I don't really care). If I want special behavior, then sure, defining operator== might make sense, and then it should obviously take precedence.
But if the whole point of this new three way compare is to reduce the combinatorial explosion of things that you need to define, I don't understand the need to split the universe into {==, !=} and {<=>, <, <=, >, >=}, and never let them interact with each other.
The part I take issue with is the statement "The columns are strictly separate."
Maybe I've missed something, but I don't see why it needs to be like this. operator<=> seems to be a strict superset of operator==, because it returns information about when equality holds, (or when equivalence holds). Shouldn't that be sufficient? Also, what's going to break if you design a type where a.operator==(b) doesn't return true when a.operator<=>(b) returns strong_ordering::equal, or vice-versa?
Again, maybe I've missed something, but this seems like a mistake. They're removing all of the footguns except this last one. Why?
originally they weren't separated, but the risk for bad performance due to that was too high. The complete rationale is described here : http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p118...
especially considering you can ` = default;` them, which should be enough a lot of times.
But for types that implement <=>, I'm not sure why == isn't automagically generated.
Especially for large types (e.g. collections) in-equality can short-circuit very quickly, whereas comparison may need to see a large part of the collection before being able to return.
The most pathological example is two large arrays of different size, that are element-by-element equal for the first million elements. Equality can return false after seeing the size difference, but <=> needs to reach the millionth-and-1 element before being bale to return a value.
The commission was especially concerned because the two operators would be functionally equivalent - so, it would be difficult to rely on testing to make sure the equality operator is also implemented.
I'd say having == is more performant for strings.
You should get == behavior if you only define a reasonable <=>, and if you also define ==, then that definition will take precedence.
Edit: argh, no, I'm wrong. I was looking at an earlier draft. So you do have to define == as well as <=>, for mostly technical reasons. Fine, I guess that answers my question.
Perhaps you could explain how this feature is a sprawling mess exactly?
In my opinion, not only is the feature easy to understand for beginners, but it also :
1) Simplifies code - less code to write means less code to have bugs
2) Prevents people making mistakes - incompatibly defined comparison operators wont happen with <=>
3) Gives a speed boost - in some algorithms it's faster to do a<=>b rather than a < b and b > a.
You could find a deep dive article just as long about the minute details of comparison for practically any language.
Sure, it adds the `<=>` operator but I think once you've been explained once what it does it's not to hard to reason about it. That still leaves the problem of technical debt of course: for the decade to come C++ devs will have to deal with both the legacy and the modern version of comparison operators and they'll have to learn to understand and deal with both.
That's great for people who work on a codebase, but makes bridging the gaps between C++ codebases harder with every passing year. And make no mistake: I 100% guarantee there will be bugs arising from the mixed use of <=> and traditional operators.
The direction of the language is towards greater cleanliness and consistency.
But you can also be a little curious as of why some industries are using C++, because if you look hard, there are not that many language like C++. Rust is an exception, sure, but it's very recent and it's not like Rust can pretend to replace everything that is done with C++.
Do you mean in term of "you can't replace decades of base code in a single day", or do you mean that there are – according to you – scope where C++ is definitely better than Rust?
Most of those are in progress and will materialize eventually.
* const generics: landing relatively soon but still not there
* const/constexpr: support is getting better , but is still very limited right now
* lack of higher kinded types prevents things that are quite easy to do with templates. The GAT (generic associated types) is being worked on but nowhere near completion
* obviously the library ecosystem is tiny and immature compared to what C++ has to offer
Feature wise I believe that Rust will be on somewhat equal footing to C++ in a few years, at which point I won't see any reason to use C++ over Rust, except if you rely on certain libraries - or in a domain where Rusts trait system is just inferior to classes + inheritance.
I do embedded security. For context, that means I use C++ when raw performance isn't that important-- because if it were, it would be in verilog and baked into the silicon.
IMO this is because Java and python are driven by open “community processes” where anyone can influence the language. C++ standards are influenced by full members of some kind of iso national bodies, from what I remember.
The biggest issue is that the language is first defined by a standard and there are multiple implementations, which makes it much harder to iterate, and, as it is hard to get any moderately complex proposal through, often you can see the lack of an overall unified design.
I do believe that c++ lacks a strong benevolent dictator figure. Stroustup abdicated his position probably too early.
The c++ standards need to focus on adding to developer productivity by incorporating micropython to make it more accessible.
The spaceship operator is exactly an attempt to make the language more accessible, but of course is being dismissed here as anything c++.
It seems to me they're using different terminology for concepts that aren't different in math? In math, "equality" (=) already means the same thing as substitutability. A non-substitutable equality is already called "equivalence" (≡).
So in math we already have these:
[1a] Non-strict partial order: a binary ordering that allows incomparability (≼, ≡, ≽, ?)
[1b] Strict partial order: like [1a], but irreflexive (≺, ≡, ≻, ?)
[2a] Non-strict weak order: like [1a], but with all elements comparable (≼, ≡, ≽)
[2b] Strict weak order: like [1b], but with all elements comparable (≺, ≡, ≻)
[3a] Non-strict total order: like [2a], where the equivalence is equality (≤, =, ≥)
[3b] Strict total order: like [2b], where the equivalence is equality (<, =, >)
If I didn't make a mistake above, then:
- C++'s "strong total ordering" seems to be what in math we call "strict total ordering"
- Their "weak total ordering" seems to be what in math we call "strict weak ordering"
- Partial order is the same thing for both
Am I wrong here? If yes, how? If not, why did they randomly invent their own terminology? I haven't seen their definitions used elsewhere.
My experience is that what C++ is calling a "weak order", and what you are calling a "weak order", is what in math is called a "pre-order" or a "quasi-order".
Meanwhile, the distinction you are making between strict and nonstrict is just ignored (except by constructivists), since they're equivalent ways of talking about the same thing. Indeed I'm not sure why you included both because, well, they're just two ways of talking about the same thing (again, unless you're a constructivist).
Really (assuming classical logic) there's just 4 possibilities here:
1. Total order (what they're calling a "strong ordering") 2. Total preorder (what they're calling a "weak ordering") 3. Partial order (which they are also calling a "partial ordering") 4. Partial preorder (which they don't account for)
"Preorder" is just a (better-known?) synonym for "non-strict weak order" [1] [2], so we don't disagree there.
"Strict" vs. "non-strict" I merely included because C++ comparisons return strict orders. I thought it was worth including, but feel free to ignore it.
So just as you pointed out in your own list, and just as I've been saying, "strong total order" isn't the terminology (every total order is strong), and neither is "weak total order" (it means "total preorder" which is... just a total order). Like you said, they should say "total" order, "preorder" (or "weak" order as I said), "partial" order. The "strong" and "weak total" stuff is just something they seem to have invented in contradiction with the established mathematical terminology for... no reason/gain?
[1] https://en.wikipedia.org/wiki/Weak_ordering#Total_preorders
[2] http://fitelson.org/roberts_measurement_theory.pdf#page=56
I'm not sure whether I agree that the terminology is confusing; on the whole I think it isn't. The reason it's not confusing is that it sufficiently different from usual math terminology so as not to interfere -- i.e., the terminology doesn't actually disagree at any point, it's not incompatible. Like, concepts get reinvented all the time and you just kind of have to get used to things having multiple terms, and be ready to translate unusual terminology into standard terminology, even as of course you should do what you can to reduce this happening. As long as you don't end up in a situation where one word means two different things, there's not really confusion, just different terminology.
And, as I said above, I definitely disagree that the article is confusing on this point, because they're very explicit about what they mean.
> the terminology doesn't actually disagree at any point, it's not incompatible
It does disagree though? I thought I just explained this... I'll do it again. "Total orders" are by their very definition in math always 'strong' -- their entire point is to use equality as the equivalence relation. That's what distinguishes them from weak orders, which can have other equivalence classes. So a "weak total order" makes no sense -- if a weak order is total, it's by definition the same as a 'strong' total order. That's in direct contradiction with their terminology.
In mathematics the word "weak" plays a similar role; e.g. in differential equations a weak solution need not be a solution; it's easy to find more examples. Similarly when one talks about a "non-Y X" or a "X without Y" where ordinarily Y is part of the definition of X. The result is not an X, but it's still (usually) clear what's meant, and these are still the terms that get used. Anyway, the point is, new terms someone is defining have to be considered on the whole.
An actual incompatibility, like I said, would be giving an existing phrase a new meaning. E.g. if they had referred to total preorders as partial orders, that would be an incompatibility.
This is what they're doing!! They're calling pre-orders "weak total orders". That's a direct incompatibility... "weak total order" already means "total order", just like "total weak order" already means "total pre-order" which already means "total order". "Weak" and "total" are both adjectives, and they're interchangeable. If you asked anyone (who unlike you had already heard of the term "weak order" before) that's exactly how they would interpret it. Nothing in it would be left open for interpretation since everything is defined.
Whereas in your solution example, unlike here, the phrase "weak solution" didn't already mean something else, and there was no existing term for the concept either. And unlike in "ring without associativity", they use the word "total" in "weak total order" to mean nothing. They could've taken it out and "weak order" would've meant exactly what they meant.
If you want to make a comparison, what they're doing would be like using "a nonnegative positive solution" to mean "a nonnegative solution" (rather than "a positive nonnegative solution"). Or using "an fractional real number" to mean "a fractional complex number" rather than a "real fractional number" (i.e. real fraction). Which would be completely nuts.
No. Giving one thing two names is not an incompatibility. Giving two things one name is an incompatibility.
> "weak total order" already means "total order"
Does it? I've never heard it called that. I think anyone on hearing the term "weak total order" would reasonably infer it refers to some notion than a total order.
> "Weak" and "total" are both adjectives, and they're interchangeable.
No. This is completely wrong. Terminology is very frequently not compositional in such a simple way.
I mean, this works perfectly fine with words that convey additional conditions. It does not work with words that convey a removal of conditions, which is what the word "weak" does!
Like, in the phrase "weak order" (meaning total preorder), the word "weak" is not imposing the conditions of reflexivity, transitivity, etc. It is starting from a baseline of "order" meaning "total order", and then weakening this to a preorder. The word "weak" only weakens!
Anyone, on seeing the phrase "weak total order", assuming they know the general usage of the word "weak", can reasonably infer that it refers to something weaker than a total order. (Likely a preorder.)
Yes, this makes "weak total order" something of a ridiculous phrase, given existing terminology. But again, remember that "weak order" is starting from a baseline where "order" means "total order"; in a sense, "weak order" is really something of an abbreviation for "weak total order".
(...of course, all of this highlights the odd way that terminology for orders themselves work. After all, "partial" is also a weakener. I haven't studied the history, but I'd bet you that "order" originally meant "total order" (it's still often used that way), then "partial order" came later as a weakener, then the meaning of "order" shifted as the study of partial orders became more common, then "total order" was coined as a retronym.)
> If you want to make a comparison, what they're doing would be like using "a nonnegative positive solution" to mean "a nonnegative solution" (rather than "a positive nonnegative solution"). Or using "an fractional real number" to mean "a fractional complex number" rather than a "real fractional number" (i.e. real fraction). Which would be completely nuts.
All of these are examples where you're using two terms that both impose conditions, rather than removing them. The word "weak" simply does not work that way.
All of these? Really? "Fractional" and "real" are 'imposing' conditions on 'number' rather than removing them? Like you said, I'd bet you that 'number' first meant 'natural number' rather than 'complex number'.
And before you tell me how deletion is also commutative just like addition—I could debate you the merits of that in natural language too, but that's beside my point in the last paragraph.
> Does it? I've never heard it called that.
Yes? That's precisely why I just gave you 2 links to people calling it exactly that above!! https://en.wikipedia.org/wiki/Weak_ordering#Total_preorders http://fitelson.org/roberts_measurement_theory.pdf#page=56
And I already asked you how you think a mathematician who unlike you knows 'weak' already has a definition this context would interpret 'weak total order' to mean? and you just ignored me there too. Just like you ignored my links way above where I showed you this is known terminology you're merely not aware of. I don't know why you're not cooperating but I'm tired of continuing.
In a strong ordering, two objects can only by one smaller, equal or larger than the other. If they are equal, it means that they are substitutable.
In a weak ordering, two objects can only be one smaller, equivalent or larger than the other. No substitutability is implied.
In a partial ordering, two objects can be one smaller, equivalent or larger than the other, or just not comparable. Again, no substitutability is implied.
There is no point in distinguishing strict vs non-strict: depending on whether you call < or <= you will get the string or not string variant, and the same for > and >=.
BTW the new language standards do make backwards incompatible changes. C++17, for example, deletes several features which were deprecated.
And [1] is an egregious example.
Doing without backwards compatibility is easy: take Rust or D.
In the same way it is fascinating to watch a forest fire from afar.
The ability to avoid rewriting is a practical thing.
The values of these comparison categories can be compared against the literal 0 (not any int, not an int whose value is 0... just the literal) using any of the six comparison operators...
IIUC it's referring to how you can safely evaluate the return value from a spaceship: by comparing against literal zero. (not how you would overload a comparison with literal zero).
It is a bit worrying that such an overloaded meaning is added again to the language.
Potential candidates: Rust, Julia, Swift.
All three are modern languages with modern concepts. I have high hopes especially for Julia.
Outside Apple platforms, maybe Rust, but it still found lacking in tooling and libraries versus what C++ offers, specially in graphics programming, GPGPU, embedded platforms, and IDEs.
Maybe now that Microsoft is looking into it, we might get Visual Rust of some sort.
Julia is more a replacement for Python than anything else.
Then if having a GC around is not a problem for the task being solved, there are plenty of alternatives out there, Java, C#, F#, OCaml, Haskell, Lisp, Scheme, ....
For games, it will highly depends what kind of game, of course. Assuming cutting-edge 3d-graphic intensive video-game, it will be probably not be your language of choice, especially regarding available out of the box libraries. For implementing Tetris, I guess you make it in any language for sufficient performance. :)
C++20 is now more aware that this things are used for comparison, and it helps to make definitions shorter.
Still handles non-totally-ordered cases fine.
I thought the motivation was that sort can be more efficient when each comparison can return more information (the standard library already has a sort function that relies only on using less-than operations).
But people eventually realized that certain operations have to be implemented together to make sense. For instance, the sort function that relies only on less-than operations defines two values as equal if neither value is less than the other. Many people consider this weird, and wonder why sort doesn’t require both less-than and equality operations. The spaceship operator essentially implements a group of operations, and guarantees they’ll be consistent: less-than, equal, and greater-than (plus not-equal, less-than-or-equal, and greater-than-or-equal). Personally, I’m not thrilled about a special purpose solution to a single example of a problem (use this one operator to implement this group of related operations), but I do see some value in making it easy to implement this group of related operations.
Similarly, recent-ish innovations like std::move and std::unique_ptr may look complicated at first, but they genuinely made life a lot easier.
Imagine, for example, an engineer decided to reorder members in a struct to make it pack better. Now the semantics of default <=> have changed!
Also, as a minor nit, the optional number sample has a possible bug. I would assume that two null optionals would compare equivalently. Or is that part of how <=> should work? Should NaN <=> NaN == partial_ordering::unordered?
Note that floating point is already weird, because most languages make == reflect the ordered equals, not the unordered equals, and so the primitive equality for floats violates the reflexive principle (i.e., x == x returns false).
Otherwise you may have the strange behavior that two erroneous values are equal, e.g., 0*inf == tan(inf).
For what it's worth the mathematical definition of partial orders suggests having NaN equivalent to NaN. You're not really forced to but giving up reflexivity doesn't seem worth it (unless you want to view each NaN a it's own object).
Interestingly mathematics only defines <= for a specific kind of object. Although on it's own this doesn't give you much information about what kind of relation it is.
Can someone please write the 3-minute blog post that is easy to understand and follow?
If the answer is "it's too complicated to explain in 3 minutes" then I think that is a telling sign.
"The TL;DR is that there's a new operator, <=>, that returns less than 0, 0, or greater than zero, just like, say, strcmp does, but for all sorts of C++ objects. You can define operator<=> and operator== and your compiler will take care of the various other comparators. Doing this speeds up some library functions, doesn't force you to write as much code, and makes comparisons more intuitive.
"There are also a bunch of corner case optimizations but if you don't care about them you don't need to know"
This was written by someone who cares about the corner cases and underlying theory. It's like FP: IEEE743 is full of weirdo cases that some really smart people spent a lot of time worrying about. All most users care about is that "they have a fractional representation and that == doesn't reliably work except against 0.0." Just because there's hundreds of pages in that spec doesn't make it dumb either.
auto operator<=>(const T&) const = default;
bool operator==(const T&) const = default;