std::sort - 传递错误的比较函数是否属于未定义行为？

Question

请问需要翻译成哪种语言？

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

如果lhs == rhs，则lambda(lhs，rhs)和lambda(rhs，lhs)都将返回true，这违反了提供严格的弱排序的要求。然而，标准是否明确标记传递这样的比较器为未定义行为？

- user2478832

---

如果行为定义得很好，那么像Visual C++调试运行时这样的编译器在运行时就不会对这样的结构进行“assert”操作，在非调试运行时，只需让代码继续执行并破坏排序即可。 - PaulMcKenzie

Answer 1

警告：以下为极端的语言律师内容。

最新标准草案中[alg.sorting]p3的措辞如下：

对于所有需要使用Compare的算法，都有一个使用operator<的版本。也就是说，comp(*i, *j) != false默认为*i < *j != false。除了25.4.3中描述的算法之外，comp应该在值上引起严格弱序。

通过使用“应该”这个词，标准暗示违反它会导致未定义行为。

无论这是否要求给定函数对所有可能的值都施加SWO，还是仅针对算法提供的值，从标准上并不清楚。但是，由于该限制陈述在讨论特定算法的段落中，因此假设它指的是提供给算法的值范围并不是不合理的。

否则，默认的operator<无法对float进行SWO，这要归功于NaN。

- Nicol Bolas

---

从语言律师的角度来看，“这些值”指的是要排序的范围内的实际值，对吗？与某些替代宇宙中可能存在的独角兽相对。因此，如果我有一种方法可以知道范围内没有两个元素是等价的，那么我应该能够在没有 UB 的情况下使用该比较器。 - rici

@rici：已将细节添加到答案中。 - Nicol Bolas

@rici 一个元素可以与自身合法比较，此时“严格弱序”的“严格”部分开始发挥作用。因此，除非您知道范围为空（这将使问题变得相当无聊），否则违反反身性的比较器仍然不好。 - Igor Tandetnik

@IgorTandetnik：说得好。我敢打赌它不会这样做，但我没有在标准中看到任何保证。（而Nicol有关NaN的有趣观察仍然存在，对吧？） - rici

@rici 为了将一个不在范围内的元素传递给比较器，std::sort需要构造这样一个元素，但它无法这样做（它只允许使用移动构造函数、移动赋值运算符和swap）。在永远不可能提供给它的输入上对比较器行为进行要求是相当无意义的。因此，虽然标准文本不够精确，但我认为将“对于所有x”解释为“对于出现在被排序范围内的所有x”是合理的。 - Igor Tandetnik

Answer 2

这个问题已经在为什么如果比较函数不是小于号运算符，std::sort会崩溃？中被提出并得到了部分回答。

至少那个线程中问问题的人声称收到了一个异常。

为了从标准中概括这里与问题相关的部分，我已经突出显示了它。现在，“工作正确”的相反之处可能被解释为“未定义行为”。

25.3 排序和相关操作 [alg.sorting]

1. 25.3 中的所有操作都有两个版本：一个使用类型为 Compare 的函数对象，另一个使用 operator<。
2. Compare 用作函数对象，如果第一个参数小于第二个参数，则返回 true，否则返回 false。对于假定有一个排序关系的算法，比较器 comp 一直被使用。假定 comp 不会通过解引用的迭代器应用任何非常量函数。
3. 对于所有需要比较器的算法，都有一个使用 operator< 的版本。也就是说，comp (*i, *j) != false 默认为 *i < *j != false。对于除了在 25.3.3 中描述的算法之外的算法，为了正常工作，comp 必须在值上引入严格弱序。
4. 术语 strict 指的是一个不可自反的关系（!comp (x, x) 对于所有 x），而 weak 指的是要求不如全序那么强，但比偏序更强的要求。如果我们将 equiv(a, b) 定义为 !comp (a, b) && !comp (b, a)，那么要求 comp 和 equiv 都是传递关系：
   
   • comp (a, b) && comp (b, c) 意味着 comp (a, c)
   • equiv(a, b) && equiv(b, c) 意味着 equiv(a, c) [ 注意：在这些条件下，可以证明
     1. equiv 是一个等价关系
     2. comp 在由 equiv 确定的等价类上引入了一个良好定义的关系
     3. 所引入的关系是严格全序的。—end note ]

- BGR

---

我遇到的问题比异常还要糟糕。末尾迭代器未被引用并被拖入容器中，这导致后来程序崩溃。 - user2478832

尽管您提供的问题与此紧密相关，但并不完全相同。我问的不是代码为什么会崩溃，而是这样的代码是否明确声明为具有未定义行为。 - user2478832

Answer 3

[alg.sorting]/3 对于除25.4.3中描述的算法以外的算法，comp 必须对值产生一个严格弱排序。

[alg.sorting]/4 术语严格（strict）指的是对无自反关系的要求（对于所有的 x，!comp(x, x)）...

您的比较谓词不是严格弱排序。

- Igor Tandetnik

---

我猜我们将把这个问题留给读者来决定一个不“正确工作”的函数是否表现出未定义的行为。 - Nicol Bolas

@NicolBolas 嗯，这里有“**[defns.undefined]** 未定义行为：该国际标准不强制规定的行为”。不幸的是，似乎没有比“不能正确工作”更强烈的说法，特别是针对 std::sort。但很难理解它以任何方式，除了“表现出未定义行为”。 - Igor Tandetnik

我知道的，我只是在文字上开玩笑而已 ;) 但从语言专家的角度来看，重要的是他们要清除掉4-5个关于“正确工作”的引用，并将它们改为更严谨的说法。 - Nicol Bolas

好的，我会认为“不正确工作”意味着错误的输出，而不是崩溃。我并不是说这是正确的解释，而是标准可能应该使用更清晰严格的语言。 - user2478832

我说过：“在我看来，情况恰好相反。”但实际上，经过更多的思考，我收回了那句话……那些话对我来说实际上并没有任何意义。它们充其量只是不规范的用语，不适合出现在任何标准中（而且听起来我们都对此表示同意）。 - Don Hatch