使用基数排序实现 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 Requires：RandomAccessIterator 应满足 ValueSwappable (17.6.3.2) 的要求。 *first 的类型应满足 MoveConstructible（表 20）和 MoveAssignable（表 22）的要求。

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

实际上，比较两个寄存器宽度值

a<b

比提取数字并比较这些数字的序列要快得多，即使我们使用位或十六进制数字也是如此。当然，这是一个常数因子差异，但提取和比较 32 个单独的位将比直接比较慢大约 100 倍。这击败了大多数理论上的担忧，特别是因为在当今的计算机上

log N

不可能真正达到 100。

Answer 2

在适当的时候使用基数排序的重载实现 std::sort 是否合法？

扩展命名空间 std - cppreference.com

向

std

添加声明

向命名空间

std

或嵌套在

std

中的任何命名空间添加声明或定义是未定义的行为，但下面指出了一些例外情况。

所以你的问题的答案是否定的。