std::sort - 是否传递了错误的比较器未定义行为？
std::sort - is passing a faulty comparator undefined behavior?
考虑这段代码：
std::sort(vec.begin(), vec.end(),
[](const Foo& lhs, const Foo& rhs) { return !(lhs < rhs); }
);
如果 lhs == rhs，lambda(lhs, rhs) 和 lambda(rhs, lhs) 都将 return 为真，这违反了提供 strict 的要求弱排序。但是，标准是否明确将传递此类比较器标记为未定义行为？
[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) ...
您的比较谓词不是严格的弱排序。
这已经在 Why will std::sort crash if the comparison function is not as operator <? 中被问到并得到了某种程度的回答。
至少那个线程中提出问题的人声称收到了 异常。
这里根据标准进行总结，我突出显示了与问题相关的部分。现在 "work correctly" 的反义词可以解释为 "undefined behavior".
25.3 Sorting and related operations [alg.sorting]
- All the operations in 25.3 have two versions: one that takes a function object of type Compare and one that uses an
operator<.
- 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.
- 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.
- 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
- equiv is an equivalence relation
- comp induces a well-defined relation on the equivalence classes determined by equiv
- The induced relation is a strict total ordering. —end note ]
警告：极端 language-lawyering 如下。
the most recent draft of the standard的措辞在[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.
用"shall"这个词，标准就是implicitly stating that violating it leads to undefined behavior。
这是否要求给定函数对所有可能值或仅对给定算法的值强加 SWO 从标准中不清楚。但是，由于限制是在谈论那些特定算法的段落中陈述的，因此假设它指的是提供给算法的值的范围并不是不合理的。
否则，由于 NaN，默认 operator< 无法对 float 施加 SWO。
考虑这段代码：
std::sort(vec.begin(), vec.end(),
[](const Foo& lhs, const Foo& rhs) { return !(lhs < rhs); }
);
如果 lhs == rhs，lambda(lhs, rhs) 和 lambda(rhs, lhs) 都将 return 为真，这违反了提供 strict 的要求弱排序。但是，标准是否明确将传递此类比较器标记为未定义行为？
[alg.sorting]/3 For algorithms other than those described in 25.4.3 to work correctly,
comphas 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 allx) ...
您的比较谓词不是严格的弱排序。
这已经在 Why will std::sort crash if the comparison function is not as operator <? 中被问到并得到了某种程度的回答。
至少那个线程中提出问题的人声称收到了 异常。
这里根据标准进行总结，我突出显示了与问题相关的部分。现在 "work correctly" 的反义词可以解释为 "undefined behavior".
25.3 Sorting and related operations [alg.sorting]
- All the operations in 25.3 have two versions: one that takes a function object of type Compare and one that uses an operator<.
- 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.
- 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.
- 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
- equiv is an equivalence relation
- comp induces a well-defined relation on the equivalence classes determined by equiv
- The induced relation is a strict total ordering. —end note ]
警告：极端 language-lawyering 如下。
the most recent draft of the standard的措辞在[alg.sorting]p3中是这样写的：
For all algorithms that take
Compare, there is a version that usesoperator<instead. That is,comp(*i, *j) != falsedefaults to*i < *j != false. For algorithms other than those described in 25.4.3, comp shall induce a strict weak ordering on the values.
用"shall"这个词，标准就是implicitly stating that violating it leads to undefined behavior。
这是否要求给定函数对所有可能值或仅对给定算法的值强加 SWO 从标准中不清楚。但是，由于限制是在谈论那些特定算法的段落中陈述的，因此假设它指的是提供给算法的值的范围并不是不合理的。
否则，由于 NaN，默认 operator< 无法对 float 施加 SWO。