6

Consider this code:

std::sort(vec.begin(), vec.end(),
    [](const Foo& lhs, const Foo& rhs) { return !(lhs < rhs); }
);

If lhs == rhs, both lambda(lhs, rhs) and lambda(rhs, lhs) will return true, which violates the requirement to provide strict weak ordering. However, does the standard explicitly mark passing such a comparator as undefined behavior?

user2478832
  • 561
  • 5
  • 11
  • Well, if the behavior were well defined, then compilers such as Visual C++ debug runtime would never `assert` on such a construct at runtime, and in the non-debug runtime, just let the code go and mess up the sort. – PaulMcKenzie Jan 17 '16 at 01:37

3 Answers3

4

Warning: extreme language-lawyering follows.

The wording of the most recent draft of the standard puts it this way in [alg.sorting]p3:

For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false. For algorithms other than those described in 25.4.3, comp shall induce a strict weak ordering on the values.

By using the word "shall", the standard is implicitly stating that violating it leads to undefined behavior.

Whether this requires that the given function impose a SWO for all possible values or just for the values given to the algorithm is not clear from the standard. However, since the restriction is stated in a paragraph that is talking about those specific algorithms, it's not unreasonable to assume that it is refering to the range of values provided to the algorithm.

Otherwise, the default operator< could not impose SWO for floats, thanks to NaN.

Community
  • 1
  • 1
Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982
  • Language-lawyerly speaking, "the values" here means the actual values in the range to be sorted, right? As opposed to the unicorns which in some alternate universe might be present in the range. So if I have some way to know that no two elements in the range are equivalent, then I should be able to use that comparator without UB. – rici Jan 17 '16 at 02:32
  • @rici: Details added to the answer. – Nicol Bolas Jan 17 '16 at 03:10
  • 1
    @rici An element could be legally compared to itself, whereupon the "strict" part of strict weak ordering kicks in. So unless you know that the range is empty (which would render the issue rather uninteresting), the comparator that violates irreflexivity is still no good. – Igor Tandetnik Jan 17 '16 at 04:51
  • @IgorTandetnik: Fair point. I'll bet it doesn't do that, but I don't see any guarantee in the standard. (And Nicol's interesting observation about NaNs remains, no?) – rici Jan 17 '16 at 04:58
  • @rici In order to pass an element to the comparator that is not already in the range, `std::sort` would need to construct such an element - but it has no way to do so (it's only allowed to use move constructor, move assignment operator and `swap`). It would be rather pointless to place requirements on the behavior of a comparator on input that can never possibly be given to it. So, while the text of the standard is imprecise, I deem it reasonable to read, say, "for all `x`" as "for all `x` that appear in the range being sorted". – Igor Tandetnik Jan 17 '16 at 05:29
  • Extreme language-lawyering is exactly what's needed for this question, thanks! – user2478832 Jan 17 '16 at 07:01
  • I wonder why they parted from the clear "undefined behaviour" and opted for the more roundabout "shall". – Catriel May 01 '23 at 13:50
  • @rici says "I'll bet it doesn't do that," You'd lose your money :-) I've seen at least one commonly used implementation of std::sort that does, indeed, compare an element with itself. Yes, it's surprising and implies the algorithm is suboptimal in at least some situations (namely when the running time is comparator-bound). – Don Hatch Jun 13 '23 at 01:17
2

This has already been asked and kind of answered in Why will std::sort crash if the comparison function is not as operator <?.

At least the person in that thread who asked the question claims to have received an exception.

To summarize here from the standard, I have highlighted the part relevant to the question. Now the opposite of "work correctly" could be interpreted as "undefined behavior".

25.3 Sorting and related operations [alg.sorting]

  1. All the operations in 25.3 have two versions: one that takes a function object of type Compare and one that uses an operator<.
  2. Compare is used as a function object which returns true if the first argument is less than the second, and false otherwise. Compare comp is used throughout for algorithms assuming an ordering relation. It is assumed that comp will not apply any non-constant function through the dereferenced iterator.
  3. For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp (*i, *j) != false defaults to *i < *j != false. For algorithms other than those described in 25.3.3 to work correctly, comp has to induce a strict weak ordering on the values.
  4. The term strict refers to the requirement of an irreflexive relation (!comp (x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering. If we define equiv(a, b) as !comp (a, b) && !comp (b, a), then the requirements are that comp and equiv both be transitive relations:
    • comp (a, b) && comp (b, c) implies comp (a, c)
    • equiv(a, b) && equiv(b, c) implies equiv(a, c) [ Note: Under these conditions, it can be shown that
      1. equiv is an equivalence relation
      2. comp induces a well-defined relation on the equivalence classes determined by equiv
      3. The induced relation is a strict total ordering. —end note ]
Community
  • 1
  • 1
BGR
  • 669
  • 5
  • 10
  • What I had was worse than an exception. end iterator was unreferenced and dragged into the container, which lead to a crash later on. – user2478832 Jan 17 '16 at 02:14
  • While the question you linked is closely related, it's not exactly the same. I'm not asking why the code may crash, but rather if such code is clearly stated as having undefined behavior. – user2478832 Jan 17 '16 at 02:16
1

[alg.sorting]/3 For algorithms other than those described in 25.4.3 to work correctly, comp has to induce a strict weak ordering on the values.

[alg.sorting]/4 The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x) ...

Your comparison predicate is not a strict weak ordering.

Igor Tandetnik
  • 50,461
  • 4
  • 56
  • 85
  • 1
    I guess we'll leave it an excersize for the reader to decide if a function which does not "work correctly" exhibits undefined behavior. – Nicol Bolas Jan 17 '16 at 01:38
  • @NicolBolas Well, there's "**[defns.undefined]** *undefined behavior*: behavior for which this International Standard imposes no requirements". Unfortunately, there doesn't appear to be anything more emphatic than "doesn't work correctly" for `std::sort` specifically. But it's hard to understand it in any way other than "exhibits undefined behavior". – Igor Tandetnik Jan 17 '16 at 01:40
  • 1
    I'm aware of that; I was being facetious through text ;) But from a language pedant point of view, it is important for them to weed out the 4-5 references to "work correctly" and change them to something more rigorous. – Nicol Bolas Jan 17 '16 at 01:42
  • Well, I would assume that "doesn't work correctly" implies wrong output, not crashing. I'm not saying that it's the correct interpretation, rather that the standard probably should have used clearer and more strict language. – user2478832 Jan 17 '16 at 02:10
  • @user2478832: I would define "works correctly" as "produces a permutation such that the comparison algorithm would identify every element as being greater than or equal to every element that precedes it", and "works incorrectly" as producing any other permutation. That would be the most logical definition of "works incorrectly" which would distinguish it from jumping the rails entirely. – supercat Mar 17 '19 at 19:25
  • @user2478832: so, if I understand correctly, you're saying you think the wording seems to imply that passing a non-SWO is *not* UB. It looks the opposite to me; however, our opinions are arguably moot, at this point, given that, in practice, the heavily used standard implementations of std::sort with which I'm familiar do treat a non-SWO as UB (e.g. crashes, out-of-bounds array accesses, infinite loops) and that's not likely to change until/unless the standard is changed to clearly say otherwise. (That will be a good day, IMO; I've seen a lot of time wasted on the fact that this is UB.) – Don Hatch Jun 13 '23 at 01:32
  • I said "It looks the opposite to me;" Actually, after more thought, I retract that... those words actually don't imply *anything* to me one way or another. They are, at best, sloppy language that don't belong in any standard (and it sounds like we all agree on this). – Don Hatch Jun 13 '23 at 02:04