是什么导致 std::sort() 访问超出范围的地址

Question

我知道要使用 std::sort() ，比较函数必须是严格的弱顺序，否则会因访问地址越界而崩溃。（https://gcc.gnu.org/ml/gcc-bugs/2013-12/msg00333.html)

但是，当比较函数不是严格的弱序时，为什么 std::sort() 会访问越界地址？它试图比较什么？

另外我想知道 STL 中是否还有其他我应该注意的陷阱。

Answer 1

首先，使用不符合要求的比较器调用算法是未定义的行为，任何事情都会发生......

但除此之外，我假设您有兴趣了解如果比较器不好，哪种类型的实现最终可能会访问越界。 实现在首先访问元素之前是否应该检查边界？IE。在调用比较器之前

答案是性能，这只是可能导致此类问题的原因之一。排序算法有不同的实现，但通常情况下， std::sort 建立在快速排序的变体之上，该变体将在不同的排序算法（如合并排序）上退化，以避免快速排序最坏情况的性能。

快速排序的实现选择一个主元，然后围绕该主元对输入进行分区，然后对两侧进行独立排序。选择枢轴的策略有多种，但常见的策略是三个的中位数：该算法获取第一个、最后一个和中间元素的值，选择三个元素的中值并将其用作枢轴值。

从概念上讲，分区从左侧开始，直到找到不小于主元的元素，然后从右侧开始尝试找到小于主元的元素。如果两个游标相遇，则分区完成。如果发现不合适的元素，则交换值，并且该过程在两个游标确定的范围内继续。从左侧开始查找要交换的元素的循环如下所示：

while (pos < end && value(pos) < pivot) { ++pos; }

虽然一般情况下分区不能假设主元的值在范围内，但快速排序 知道 确实如此，毕竟它从范围内的元素中选择了枢轴。在这种情况下，常见的优化是将中值交换到循环的最后一个元素中。这保证了 value(pos) < pivot 将会是真的 前 pos == end （最坏的情况下： pos == end - 1）。这里的含义是我们可以放弃对范围末尾的检查，并且可以使用 unchecked_partition （选择您选择的名称）具有更简单更快的条件：

while (/*pos < end &&*/ value(pos) < pivot) ++pos;

一切都很好，除了 < 拼写为 comparator(value(pos), pivot). 。现在如果 comparator 未正确实施，您最终可能会得到 comparator(pivot,pivot) == true 并且光标将超出范围。

请注意，这只是可以删除性能边界检查的算法优化的一个示例：假设有效订单，则 不可能的 如果快速排序将枢轴设置为最后一个元素，则走出上述循环中的数组 前 调用这个修改后的分区。

回到问题：

实现在首先访问元素之前是否应该检查边界？IE。在调用比较器之前

不，如果它通过证明它不会走出数组来删除边界检查，则不会，但该证明是建立在比较器有效的前提下的。

Answer 2

std::sort确实要求给定的比较器建立严格的弱排序，否则排序并没有真正有意义。

作为访问范围的访问，您发布的链接是一个错误报告，即它不应该实际执行此操作。像任何其他软件一样的编译器可以且会有错误。正如亚当指出的那样，这个特定的错误报告被拒绝，因为它不是真正的错误。

当您没有严格的弱排序时究竟发生了什么，但是这样做并没有意义，因此由标准遗漏。因此，通过遗漏是<强烈的>未定义的。 未定义意味着任何事情都可能发生，甚至可以访问范围。

为避免“陷阱”只需要了解您使用的算法和功能的要求。对于C ++有一个很好的参考网址，我通常使用： cppreference

在 std::sort 的页面说：

comp - 比较函数对象（即满足比较要求的对象），如果第一个参数小于（即之前订购），则返回true。

与比较