标准存储桶或计数排序

Question

我一直想知道为什么C++标准模板库似乎没有标准的存储桶/库(分发)排序。这些在现代编程中似乎没有得到充分利用，显然是因为需要一种将对象转换为整数以进行排序的方法。两者对我来说似乎都相对简单，所以为什么我们不把它放在库中呢？

template<class RandomAccessIterator, class Index, class index_type=unsigned int>
void std::distribution_sort(
        RandomAccessIterator begin,
        RandomAccessIterator end
        index_type minval,
        index_type maxval,
        Index indexer,);

unsigned int indexer(const std::string& word) 
{
    switch(word.size()) {
    case 0: return 0;
    case 1: return (word[0]<<24);
    case 2: return (word[0]<<24) | (word[1]<<16);
    case 3: return (word[0]<<24) | (word[1]<<16) | (word[2]<<24);
    default: return (word[0]<<24) | (word[1]<<16) | (word[2]<<8) | (word[3]);
    }
}

int main() {
    std::vector<std::string> data;
    data.push_back("");
    data.push_back("APPLES");
    data.push_back("banana");
    std::distribution_sort(data.begin(), data.end(), 0, ~0, indexer);
} 

Answer 1

对我来说似乎都相对简单，所以为什么我们不把它放在库中呢？

很多事情都很简单。这不是将它们放在库中的好理由。

我认为原因可能是std::sort在大多数情况下都足够好。

Answer 2

出于同样的原因，没有ASCII到EBCDIC的转换，数据库连接，自然语言分析，文本到语音合成和一大堆其他功能。

每个决策都有机会成本(意味着通过做其他事情而放弃的所有事情)，而标准是程序员和实施者之间的合同。

我希望能够写出这样的程序：

int main (void) {
    std::accountingApplication();
    return 0;
}

而不是必须实际编写会计应用程序，但我担心实现者可能会在提供这种级别的功能时犹豫不决。

此外，对于大多数情况，C和C++都有一个非常好的排序函数。如果事实证明这不取决于某人拥有的特定数据，他们将被期望编写自己的数据。

如果标准增加了存储桶排序，为什么要止步于此呢？为什么不为所有类型的数据分布提供单独的排序(即使是备受诟病的冒泡排序在小集合或已经排序的集合上也能很好地工作)？

因为这一推理将在2166年而不是2025年左右为我们提供下一个C++标准，这就是为什么:-)

有关这些要点的更详细解释，请参阅this related answer。

顺便说一句，我不确定将对象转换为可分配整数的要求是不是一个问题--这可以通过回调(如qsort中的比较函数)或标准方法(如Java的toString)轻松解决。