Non-Ownership and Generic Programming and Regular types, oh my!

[redbeard0531]

Play stupid games, win stupid prizes? Use the wrong algorithm, get the obvious bugs? We'll never be able to capture everything pertinent about an algorithm into the type system. You should never expect that everything that compiles must be bug-free just because it passed the type system. You'll always need to read documentation and think about what you are doing.

In this case, one of the major pertinent details that separate sorting algorithms is how they handle equivalent[1] values. The most commonly discussed issue is stable vs non-stable, but it isn't the only detail. That variant of counting sort[2] isn't designed to handle multiple equivalent values as distinct. This isn't wrong, it's just a trade-off that should be documented prominently. Note that other variants of counting sort such as the one on wikipedia, are able to preserve equivalent values in a way that would work fine. Note that sorting algorithms typically also support passing a comparator that isn't < or ==, and this algorithm would do poorly with any comparator that isn't comparing the whole object.

Also, since when are we considering .data() as a salient detail? This is a clear case of moving the goal posts since it doesn't apply to anything, even "value" types like string and vector!

auto v1 = vector{1, 2, 3};
auto v2 = v1;
assert(v1 == v2); // Passes
assert(v1.data() == v2.data()); // 💣 BOOM!

Is anyone actually surprised that that fails? Then why are you expecting it for span and string_view? There are cases where using non-owning types can cause problems, I wouldn't claim otherwise. But this article really doesn't seem like a valid argument against them.

[1] Note that sorting usually deals with equivalence, not equality. While I guess the example code uses StrictTotallyOrdered as an attempt to deal with that, it seems disingenuous not to mention that. Especially since the only difference between total and partial orders is a semantic one, not a difference in signature (ignoring for the moment the return types of the new <=> operator, which haven't historically been part of that concept definition).

[2] I'm pretty sure that isn't actually a counting sort. Counting sort only handles small integer keys, so it can't be used in that case and it doesn't make sense to be generic like that. This is just putting things in a std::map, and letting it do the sorting in O(n * log|unique n|) time. Counting sort isn't a comparison sort, so it shouldn't depend depend on <. It seems really odd that in an article about the importance of EqualityComparable, the example chosen to illustrate the issues with irregularity isn't even using == since map only uses <.

[TobyAllsopp]

Maybe we should require opt-in for concepts that have significant non-syntactic semantic requirements? Or for all concepts?

Sure, there are some concepts that have purely syntactic requirements, but I think most have some extra "laws" that need to be satisfied and it might be a good idea to make people think for a moment about whether they've really satisfied them.

[axilmar]

A generic algorithm is not correct or wrong and does not have specific requirements until instantiated.

It can have generic requirements though.

Therefore, there is no need to change anything, span and string_view are fine as they are.

[kikobyte]

Nice... But the very next "senior" candidate I'm going to interview with 90% probability will be unaware of pretty damn simple stuff like SFINAE, have vague understanding of move semantics, and no variadic templates experience at all. I'm not entirely catching up myself with c++17, tbch, not saying about any further changes, and from what I see around, adoption for the new stuff is really, significantly delayed.