標準存儲桶或計數排序

我一直在想，爲什麼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

標準存儲桶或計數排序

回答

相關問題