Effective STL理解你的排序操作

排序一直是數據結構中的常用算法，STL提供的排序算法非常豐富，如何有效 使用就值得探討。在網上沒有找到條款31的翻譯，於是我自己翻譯了。－－ Winter

如何進行排序？讓我數數有幾種方法。

一旦程序員需對容 器元素進行排序，sort算法馬上就會出現在他的腦海(可能有些程序員會想到 qsort，但詳細閱讀條款46後，他們會放棄使用qsort的想法，轉而使用sort算法 )。

sort是一個非常優秀的算法，但並當你並不真正需要它的時候，其實 就是一種浪費。有時你並不需要一個完整的排序（簡稱為全排序）。例如，你現 有一個包含Widget對象（Widget意為“小掛件”）的vector容器，並 且你想把其中質量最好的20個Widget送給你最好的客戶，那麼你需做的只是找出 這20個質量最好的Widget元素，剩下的並不需關心它們的順序。這時你需要的是 部分排序（相對於全排序），恰好在算法中就有一個名副其實的部分排序函數函 數：partial_sort：

bool qualityCompare(const Widget& lhs, const Widget& rhs)
{
　　// lhs的質量不比rhs的質量差時返回true，否則返回false
}
…
partial_sort (widgets.begin(), 　　// 把質量最好的20元素
　　widgets.begin() + 20,　　　// 順序放入widgets容器中
　　widgets.end(),
　　qualityCompare);
… 　// 使用 widgets...

通過調用partial_sort，容器中開始的20個元素就是你需要的質量最好的20 個Widget，並按順序排列，質量排第一的就是widgets[0], 緊接著就是widgets [1]，依次類推。這樣你就可以把質量第一的Widget送給你最好的顧客，質量第 二的Widget就可以送給下一個顧客，很方便吧，更方便的還在後面呢。

如果你只是想把這20個質量最好的Widget禮物送給你最好的20位顧客，而不需要 給他們一一對應，partial_sort在這裡就有些顯得大材小用了。因為在這裡，你 只需要找出這20個元素，而不需要對它們本身進行排序。這時你需要的不是 partial_sort，而是nth_element。

nth_element排序算法只是對一個區 間進行排序，一直到你指定的第n個位置上放上正確的元素為止，也就是說，和 你進行全排序和nth_element排序相比，其共同點就是第n個位置是同一個元素。 當nth_element函數運行後，在全排序中應該在位置n之後的元素不會出現在n的 前面，應該在位置n前面的元素也不會出現在n的後面。聽起來有些費解，主要是 我不得不謹慎地使用我的語言來描述nth_element的功能。別著急，呆會兒我會 給你解釋為什麼，現在先讓我們來看看nth_element是如何讓質量最好的20個 widget禮物排在vector容器的前面的：

nth_element (widgets.begin(),　// 把質量最好的20元素放在
　　widgets.begin() + 20,　　 // widgets容器的前面,
　　widgets.end(),　　// 但並不關心這20個元素
　　qualityCompare);　　//本身內部的順序

你可以看出，調用nth_element函數和調用partial_sort函數在本質上沒有區 別，唯一的不同在於partial_sort把前20個元素還進行排列了，而nth_element 並不關系他們內部的順序。兩個算法都實現了同樣的功能：把質量最好的20個元 素放在vector容器的開始部分。

這樣引起了一個重要的問題：要是質量 一樣的元素，排序算法將會如何處理呢？假設有12個元素的質量都為1（最好等 級），15個元素的質量等級為2（質量次之），如果要選擇20個最好的Widget， 則先選12個質量為1的元素，然後從15個中選出8個質量為2的元素。到底 nth_element和partial_sort如何從15個中選出8個，依據何在？換句話說，當多 個元素有同樣的比較值時，排序算法如何決定誰先誰後？

對於 partial_sort和nth_element算法來說，你無法控制它們，對於比較值相同的元 素它們想怎麼排就怎麼排（查看條款19，了解兩個值相等的定義）。在我們上面 的例子中，面對需要從15個等級為2的元素選出8個增加到top 20中去，他們會任 意選取。這樣做也有它的道理：如果你要求得到20個質量最好的Widget，同時有 些Widget的質量又一樣，當你得到20個元素至少不比剩下的那些質量差，這已經 達到你的要求，你就不能抱怨什麼了。

假如對於全排序，你倒是可以得 到更多的控制權。一些排序算法是“穩定的”(stable)，在一個 “穩定”的排序算法中，如果兩個元素有相同的值，它們的相對位置 在排序後也會保持不變。例如：如果在未排序時Widget A在Widget B之前，而且 都有相同的質量等級，那麼“穩定”排序算法就可以保證在排序之後 ，Widget A仍然在Widget B之前。而非“穩定”排序算法就不能保證 這一點。

partial_sort和nth_element都不是“穩定”排序算 法，真正的“穩定”排序算法是stable_sort，從名字上看就知道它 是“穩定”的。如果你在排序的時候需要保證相同元素的相對位置， 你最好使用stable_sort，在STL中沒有為partial_sort和nth_element算法提供 對應的“穩定”版本。

說到nth_element，名字確實很怪，但 是功能卻是不少，除了讓你找到無關順序的top n個元素外，它還能找到某個范 圍的中值，或者找到在某個特定百分點的值。

vector<Widget>::iterator begin(widgets.begin()); 　 　// widgets的第一個
　　vector<Widget>::iterator end (widgets.end()); 　//和最後一個迭代器
　　//
　　vector<Widget>::iterator goalPosition; 　// 需 要定位的那個迭代器

　　　//以下代碼用來得到質量排在中間的那個元素的迭代器
　　goalPosition = begin + widgets.size() / 2; 　// 要找的那個元素應該
　　　　　　　　　　　　　　　　　　　　　　　　//在vector的中部。
　　 nth_element(begin, goalPosition, end, 　　　　// 找到容器widgets元素的 中值
　　　　　　　　　qualityCompare);　　//
　　 … // goalPosition現在指向中值元素

　　//以下代碼用來得到質量排在75%的元素
　　 vector<Widget>::size_type goalOffset = 　// 計算出要找的值
　　　　0.25 * widgets.size(); 　　//離begin迭代器的距離。
　　　　//
　　 nth_element( begin, begin + goalOffset, end, 　// 得到質量排在75％的元 素
　　　　　　　　　　　　　　 qualityCompare); 　　//

　　… 　// goalPosition 現在指向質量排在75％的元素。

當你需要把一個集合由無序變成有序時，可選用sort, stable_sort或 partial_sort，當你只需得到top n或者在某個特定位置的元素，你就可以使用 nth_element。或許有時你的需求比nth_element提供的還要少，例如：你並不需 要得到質量最好的前20個Widget，而只需要識別那些質量等級為1或者等級為2的 Widget。當然，你可以對整個vector按照Widget的質量等級進行全排序，然後查 找到第一個質量等級低於等級2的元素。

問題就在於全排序太耗費資源， 而且大部分工作都是無用功。這種情況下最好選擇partition算法，partition只 是給你確定一個區間，把符合特定條件的元素放到這個區間中。舉例來說，要把 質量等級好於等於等級2的Widget的元素放在widget容器的前端，我們可以定義 一個用於識別Widget質量等級的函數：

bool hasAcceptableQuality(const Widget& w)
　　{
　　　　//如 果w的質量等於或好於2，返回true，否則返回false
　　}

然後把這個判斷函數傳遞給partion算法：

vector<Widget>::iterator goodEnd = 　// 把所有滿足 hasAcceptableQuality
　　partition(widgets.begin(), 　　// 條件的放在widgets容器的前面，
　　widgets.end(), 　// 返回第一個不滿足條件的
　　hasAcceptableQuality); 　//元素的位置

這樣一來，所有在迭代器widgets.begin()和迭代器goodEnd之間的元素都是 滿足需求的元素：其質量等級好於或等於2。而在 goodEnd 到 widgets.end() 之間的元素的質量等級都會低於質量等級2。如果你對質量等級相同元素的相對 位置很關心的話，你可以選擇stable_partition算法來代替partition。

需要注意的是sort, stable_sort, partial_sort, 和nth_element算法都需要以 隨機迭代器(random access

iterators)為參數，因此這些算法能只能用 於vector, string, deque, 和array等容器，對於標准的關聯容器map、set、 multmap、multset等，這些算法就有必要用了，這些容器本身的比較函數使得容 器內所有元素一直都是有序排列的。對於容器list，看似可以用這些排序算法， 其實也是不可用的（其iterator的類型並不是隨機迭代器），不過在需要的時候 可以使用list自帶的排序函數sort(有趣的是list::sort函數和一個“穩定 ”排序函數的效果一樣)。如果你想對一個list容器使用partial_sort或 nth_element，你只能間接使用。一個可選的方法是把list中的元素拷貝到帶有 隨機迭代器的容器中，然後再使用這些算法；另一種是生成一個包含 list::iterator的容器，直接對容器內的list::iterator進行排序，然後通過 list::iterator得到所指的元素；第三種方法，借助一個包含iterator的有序容 器，然後反復把list中的元素連接到你想要鏈接的位置。看見了吧，你可以選擇 的方式還是比較多的。

partition 和stable_partition函數與sort、 stable_sort、partial_sort、nth_element不一樣，要求沒有那麼嚴格，輸入參 數只需是雙向迭代器(bidirectional iterator)。因此你可以對所有的標准序列 容器使用partition和stable_partition算法。

讓我們來總結一下你的排 序操作：

若需對vector, string, deque, 或 array容器進行全排序，你 可選擇sort或stable_sort；

若只需對vector, string, deque, 或 array容器中取得top n的元素，部分排序partial_sort是首選.

若對於 vector, string, deque, 或array容器，你需要找到第n個位置的元素或者你需 要得到top n且不關系top n中的內部順序，nth_element是最理想的；

若 你需要從標准序列容器或者array中把滿足某個條件或者不滿足某個條件的元素 分開，你最好使用partition或stable_partition；

若使用的list容器， 你可以直接使用partition和stable_partition算法，你可以使用list::sort代 替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效 果，你必須間接使用。正如上面介紹的有幾種方式可以選擇。

另外，你 可以使用標准的關聯容器來保證容器中所有元素在操作過程中一直有序。你還可 考慮非標准的STL容器priority_queue，它同樣可以保證其元素在所有操作過程 中一直有序(priority_queue在傳統意義上屬於STL的一部分，但根據 “STL”定義，需要STL容器支持迭代器，而priority_queue並不支持 迭代器，故不能能稱為標准STL容器)。

這時你或許會問：“性能如 何？”非常好的問題。廣義的講，算法做的工作越多，花的時間越長， “穩定”性排序算法比“非穩定”性排序算法要耗時。我 們可以按照其消耗的資源(時間和空間)的多少，對本文中討論的排序算法作個排 序，消耗資源越少的排在前面：

1. partition

2. stable_partition

3. nth_element

4. partial_sort

5. sort

6. stable_sort

選擇這些算法的依據是你的需求而不是它們 的性能。若你能選擇一個算法恰好滿足你的需求(如用部分排序代替全排序)，不 僅會清晰表達你的意圖，而且能高效的使用STL。