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

Question

对于适用的数据类型,良好的基数排序可以std::sort大大超过比较排序,但通常实施为内部排序.是否有理由不使用基数排序来实现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 排序

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

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

1效果：对[first,last)范围内的元素进行排序。

2要求：RandomAccessIterator 应满足 ValueSwappable (17.6.3.2) 的要求。*first 的类型应满足 MoveConstructible（表 20）和 MoveAssignable（表 22）的要求。

3复杂性：O(N log(N )) （其中 N == 最后 - 第一个）比较。

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