9

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

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

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

4

2 回答 2

17

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

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

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

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

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

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

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

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

一切都很好，除了<拼写comparator(value(pos), pivot)。现在，如果comparator执行不正确，您最终可能comparator(pivot,pivot) == true会遇到光标超出范围。

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

回到问题：

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

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

于 2014-06-04T22:28:14.193 回答
1

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

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

当您没有严格的弱排序时，标准没有定义究竟会发生什么，这样做没有意义，因此被标准排除在外。因此，它没有被遗漏定义。未定义意味着任何事情都可能发生，即使访问超出范围。

至于避免“陷阱”，请注意您使用的算法和功能的要求。对于 C++，我通常使用一个不错的参考站点：cppreference

在页面上std::sort说：

comp - 比较函数对象（即满足比较要求的对象），如果第一个参数小于（即排在前面）第二个参数，则返回真。

带有指向比较描述的链接

于 2014-06-04T21:47:25.590 回答