c++ - 用基数排序实现 std::sort 的重载是否合法？

Question

对于适用的数据类型，良好的基数排序可以大大击败比较排序，但 std::sort 通常实现为 introsort。是否有理由不使用基数排序来实现 std::sort？基数排序不足以实现 std::sort，因为 std::sort 只要求类型具有可比性，但对于比较和基于基数的排序产生相同结果的类型回答(例如 int)这似乎是悬而未决的果实，没有被采摘。

在适当的时候使用基数排序的重载来实现 std::sort 是否合法？ std::sort 的要求是否有什么从根本上防止这种情况发生的？

编辑:我应该更清楚一点。我在问标准库的实现是否合法。我不是在询问标准库实现的用户在 std 命名空间中放置任何东西。我知道这样做是违法的，除非在特定情况下。

Answer 1

评论引用了“假设”规则。这其实没有必要。 std::sort没有指定“好像使用了 introsort”。 std::sort 的规范很简短，只需要比较次数的效果(排序)和复杂度(O(N log N))。基数排序满足两者。

25.4.1.1 sort

template<class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

1 Effects: Sorts the elements in the range [first,last).

2 Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable (17.6.3.2). The type of *first shall satisfy the requirements of MoveConstructible (Table 20) and of MoveAssignable (Table 22).

3 Complexity: O(N log(N )) (where N == last - first) comparisons.

在实践中，比较两个寄存器宽度值 a<b比提取数字并比较这些数字的序列要快得多，即使我们使用位或十六进制数字也是如此。当然，这是一个常数因子差异，但提取和比较 32 个单独的位将比直接比较慢大约 100 倍。这打败了大多数理论上的担忧，尤其是因为 log N在今天的计算机上不可能真的是 100。