7 ms·
One of the most frustrating bugs I encountered in a previous job was an incorrect implementation of a “strict weak ordering” that would cause containers and alg
by makecheck 7y ago
One of the most frustrating bugs I encountered in a previous job was an incorrect implementation of a “strict weak ordering” that would cause containers and algorithms to just plain misbehave. The evil part was that there was a whole range of misbehavior, including “generally working” for most data, while crashing in other cases!
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!!!
- mort96 7y agoI'm working on a game. I have a templated 2D vector implementation. Tile positions use Vector2<int>, entity positions and such use Vector2<float>. 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>.
- stkdump 7y agoOh, that is simple: in associative containers, you can pass an external comparator as additional template parameter. Use that. Don't implicitly convert, it will bite you.
- mort96 7y agoOh thanks, I somehow didn't see that. That does sound better yeah.
- de_watcher 7y agoAnd also see if you're better off with an std::unordered_map or a custom sorted-array implementation of a map.
- masterjack 7y agoIn addition to the sibling’s comment on explicitly passing inna comparator, note that std::map is an ordered dictionary and requires an ordering on your elements. It sounds like you may have preferred hash_map
- mort96 7y agoI don't know, the way std::pair works is that it compares the two elements' `first`, or their `second` if `first` happens to be equal. That seems pretty good; lookup should still be O(n). I'll keep hash_map in mind though, and maybe do some performance testing to see which is actually faster.
- jcelerier 7y agostd::map is incredibly slow (and allocates willy-nilly), see https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/ https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-o... for a comparison of modern hash maps. Or at least boost::flat_map if you need ordering but don't do many insertions / removals and care instead for fast iteration on the map. 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.
- Const-me 7y agoIn some cases, the performance of std::unordered_map is fixable with a custom allocator: https://github.com/Const-me/CollectionMicrobench https://github.com/Const-me/CollectionMicrobench
- fpoling 7y agoChromium advised for their typical use cases to use std::map in favor of std::unordered_map. And they also provide own version of flat_map. [1] - https://chromium.googlesource.com/chromium/src/+/master/base/containers/README.md https://chromium.googlesource.com/chromium/src/+/master/base...
- iso-8859-1 7y agoTo enforce correctness, you'd need to demand proofs. I think the most common approach for this is dependent types. I think you'll have to wait another 20 years before they become mainstream.
- comex 7y agoPython is almost as bad as C++ when it comes to making custom classes sortable. In Python 2 there was had __cmp__, which was roughly the same as C++'s new spaceship operator, but Python 3 inexplicably removed it in favor of only having individual comparison operators like __eq__, __lt__, __gt__, etc. Oh, and functools.total_ordering, which lets you "only" define __lt__ and __eq__ and get the rest automatically implemented, but that's still two things to define when __cmp__ was only one.
- de_watcher 7y agoSo Python has reverted to the pre-C++20 state but without the ability to redefine other operators? Can you even make a proper custom float type in Python then?
- joshuamorton 7y agoYou can define all the operators explicitly if you wish. However, the common case is made easier, define only __eq__ and one of the others (__gt__ or __le__ usually) and @functools.total_ordering will derive all of the others for you.
- de_watcher 7y agoOkay, it's exactly the pre-C++20 state. That's actually funny.
- joshuamorton 7y agoI don't think that's true, python had no concept of strong vs. weak equality and ordering. cmp returned either -1, 0, or 1 (or at least, it was treated that way). There was no way to describe "unequal, but not orderable". 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.
- jcelerier 7y ago> 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”. 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.
- vnorilo 7y agoIt has saved my behind a handful of times. Also shoutout to unordered_map for the debug build runtime check that equal keys have equal hashes.
- pjmlp 7y agoMSVC also does interator validation and bounds checking in debug mode, alongside its macro based contracts. Some things are actually more productive in MS land for security conscious coding. A nice side effect from all those Windows 9X exploits.
- Const-me 7y ago> C++ compiler needs to provide robust compile-time and run-time checks to tell programmers that things are wrong 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 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/cs0660 https://docs.microsoft.com/en-us/dotnet/csharp/misc/cs0661 https://docs.microsoft.com/en-us/dotnet/csharp/misc/cs0661
- masklinn 7y ago> CS0216 forces you to implement operators in sets, e.g. can’t implement `==` without also implementing `!=` it won’t build otherwise So… that you can provide incoherent implementations of == and != instead of the system just generating one based on the other?
- Const-me 7y agoThey don’t have to return bool. 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 https://en.wikipedia.org/wiki/NaN#Comparison_with_NaN
- masklinn 7y agoI'm not saying you shouldn't be able to implement both such that they're not coherent, I'm saying requiring implementing both when the system could provide one based on the other (as e.g. Haskell, Rust or Python do) is an unforced error and a pointless footgun.
- Const-me 7y ago> unforced error and a pointless footgun 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?
- gpderetta 7y agoI do not think it is trivial to prove at compile time that an a comparison operator is correct: I think you need a fancy type system for that. Asserting correctness at runtime is of course possible, but it has non trivial cost. Most std libraries provide a debug mode that will catch these sort of issues.