标准存储桶或计数排序

我一直在想，为什么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); 
}

来源

2011-08-18 Mooing Duck

尚未投票结束，但它闻起来“没有建设性”。 – amit

呃，我猜是这样的。我应该把这个放在我的论坛上，而不是在这里。哎呀。 –

似乎都比较简单，我，所以我们为什么不有这样的图书馆吗？

很多事情很简单。这不是让他们进入图书馆的好理由。

我想原因是std::sort对大多数情况来说已经足够好了。

来源

2011-08-18 22:55:21

我写了一个distribution_sort概念证明，并在MSVC10中进行了测试。对于整数，它的运行时间只有一半，但只有在整数的数量是1000-1000000时。对于需要动态内存的对象，它在30％-50％的时间内运行。但是，它并没有击败我期待的边距。 –

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

每个决策都有一个机会成本（意味着所有的事情都是通过其他方式实现的），而标准是程序员和实施者之间的契约。

我希望能够写程序：

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

，而不必实际编写了一个会计应用程序，但我担心的实施者可以在提供电力这一水平却步。

此外，C和C++ 都有大多数情况下完美的排序功能。如果事实证明它不符合某人的具体数据，那么他们需要自己写。

如果标准添加了桶排序，为什么要在那里停止？为什么不给我们一个单独的排序来处理各种数据分布（即使是那些已经大部分排序的小集合或集合，很多恶意的冒泡排序也能很好地工作）？

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

也this related answer这些点的更详细的解释见。

顺便说一句，我不知道的是，要求你的对象转换为整数分配是个问题 - 这可能是与回调（如在qsort比较功能）或标准方法（迎刃而解像Java的toString）。

来源

2011-08-18 22:56:36 paxdiablo

实际上，我认为有些实现在std :: map之下有红黑树，等等。但是，考虑到C++ 0x已经有四种比较排序（谁使用partial_sort_copy？）我并不认为简单的分布排序是不合理的，特别是因为在小范围内排序具有唯一缺陷的数据是很常见的。是的，我们可以自己做，但是每个人都使用快速排序。 O（Nlog（N））而不是O（2N） –

@Mooing，我已经改变了红黑到数据库的东西 - 我没有把std :: map考虑进去:-) – paxdiablo

标准存储桶或计数排序

回答

相关问题