CODEWITHSUNDEEP
c++stlundefined-behavior
user2478832
user2478832

Reputation: 561

std::sort - is passing a faulty comparator undefined behavior?

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?

Upvotes: 6

Views: 1745

Answers (3)

BGR
BGR

Reputation: 709

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 ]

Upvotes: 2

Nicol Bolas
Nicol Bolas

Reputation: 473976

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.

Upvotes: 4

Igor Tandetnik
Igor Tandetnik

Reputation: 52591

[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.

Upvotes: 1

Related Questions