时间戳

首页 > 解决方案 > std::sort 可以专门使用 as-if 规则对 int* 使用冒泡排序吗？

c++ - std::sort 可以专门使用 as-if 规则对 int* 使用冒泡排序吗？

问题描述

std::sort有复杂度要求，即 O(n log n)。除了常见的 QuickSort 或 IntroSort，其他算法也适合它。

使用 O(n 2 )的冒泡排序肯定不适合。

但是，如果我们对int没有显式谓词的指针进行专门化。无法观察迭代或比较的次数，因为没有办法专门化operator<或指针间接，并且不允许用户的代码专门std::less化ints，并且由于谓词未传递，它是std::less/ operator<。

那么，int*无谓词版本可以通过 STL 的一些邪恶实现来专门使用冒泡排序吗？

这个问题类似于使用基数排序实现 std::sort 的重载是否合法？，但答案指出Radix排序符合要求，所以不是我打算问的。

实际意图是如果允许实现进行优化，这对复杂性来说更糟，但对运行时更好。我想专注于“如果允许这样做”而不是“如果这可能以更复杂的复杂性更快地实现”，这就是为什么我选择冒泡排序作为明显可怕的例子。

标签： c++sortinglanguage-lawyerbig-o

解决方案

无法观察到迭代或比较的次数

所以？算法的复杂性由标准给出，而不是某些观察者。你是否能观察到这种复杂性是无关紧要的。

25.8.2.1

  1. 复杂性：让 N 排在最后 - 首先。O(NlogN) 比较和预测。

这很清楚。另一方面，冒泡排序需要 O(n^2)，因此如果一个实现要使用冒泡排序，它将不符合标准。

我根本看不出假设规则是如何相关的。

另请注意，自定义仿函数存在重载Compare，在这种情况下，可以观察到比较的数量，即使对于原始类型也是如此。

实际意图是如果允许实现进行优化，这对复杂性来说更糟，但对运行时更好。

std::sort不，正如我上面所说，上限很明确。但是如果通过某种魔法，编译器可以排序O(1)或不使用Compare，它一定可以做到这一点。如果编译器可以证明你无法观察到是否std::sort已经被调用，那么 as-if 规则就可以在这里发挥作用。非常理论上，如果您std::sort只使用查找和访问最小元素，则编译器在此规则下允许使用简单的 for 循环查找最大值。

推荐阅读