一切複雜的排序操作,都能透過 STL 輕鬆實現!
對程式設計師而言,資料結構是必修的一門課。從查找、排序到鏈表、二叉樹,幾乎所有算法與原理都得理解,理解不了也要硬背下來。所幸這些理論多已成熟、算法也大致定型,你不需要再花心思去推翻其原理或驗證正確性。可是,當你真正用程式語言投入工作時會發現:面對不同需求,你得一次又一次用程式碼重新實作這些成熟算法,還會一再掉進因疏忽而產生的 bug 裡。這時你會渴望有個工具,早已幫你實作好這些功能,讓你隨心所欲地取用,又不影響效能——這就是 STL,標準模板庫!
西方有句諺語:不要重複發明輪子!
STL 幾乎封裝了資料結構中的所有算法,從鏈表到佇列、從向量到堆疊、從 hash 到二叉樹、從搜尋到排序、從新增到刪除……可以說,一旦你理解了 STL,就不再拘泥於算法本身,而能站在巨人的肩膀上思考更高階的應用。
排序是最廣泛的算法之一,本文將詳細說明 STL 中各種排序函數的用法與差異。
C++ 之所以廣受喜愛,是因為它兼具物件導向概念與 C 語言的高效能。STL 排序算法同樣講求效率,因此針對不同需求提供了不同的函數,而各函數背後實作的算法也不盡相同。
所有 sort 算法的參數都需要傳入一個範圍 [begin, end),且使用的迭代器必須是隨機訪問迭代器(RandomAccessIterator),也就是能以 it+n 方式隨機訪問的迭代器(partition 與 stable_partition 除外)。若你需要自訂比較方式,可以把自定義的仿函數(functor)作為參數傳入,每種算法都支持傳入比較函數。以下是所有 STL sort 系列函數:
函數名 —— 功能描述
sort —— 對給定區間所有元素排序
stable_sort —— 對給定區間所有元素進行穩定排序
partial_sort —— 對給定區間所有元素部分排序
partial_sort_copy —— 對給定區間複製並排序
nth_element —— 找出給定區間某個位置對應的元素
is_sorted —— 判斷一個區間是否已排好序
partition —— 使符合某條件的元素排在前面
stable_partition —— 相對穩定地使符合某條件的元素排在前面
其中 nth_element 最不易理解,實際上它是用來「找出第幾個」。例如:找出含 7 個元素的陣列中排在正中央那個數,此時你既不關心前面、也不在意後面,只想知道排在第四位的元素值是多少。
當你想以特定方式排序時,需要給 sort 指定比較函數,否則程式會自動提供一個預設的比較函數。
vector < int > vect; //...
sort(vect.begin(), vect.end()); //此時相當於呼叫 sort(vect.begin(), vect.end(), less<int>() );
上述例子中,系統為 sort 提供了 less 仿函數。STL 還提供了其他仿函數:
名稱 —— 功能描述
equal_to —— 相等
not_equal_to —— 不相等
less —— 小於
greater —— 大於
less_equal —— 小於等於
greater_equal —— 大於等於
要注意的是,這些函數並非都適用於你的 sort 場景,如何取捨取決於你的應用。此外,不能直接寫仿函數的名字,而要寫其重載的 () 函數:
less<int>()
greater<int>()
當容器中元素是標準型別(int、float、char)或 string 時,你可以直接使用這些函數模板。但如果你自訂型別,或想以其他方式排序,有兩種做法:一是自己撰寫比較函數,二是重載型別的 '<' 運算子。
#include <iOStream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
class myclass {
public:
myclass(int a, int b):first(a), second(b){}
int first;
int second;
bool Operator < (const myclass &m)const {
return first < m.first;
}
};
bool less_second(const myclass & m1, const myclass & m2) {
return m1.second < m2.second;
}
int main() {
vector< myclass > vect;
for(int i = 0 ; i < 10 ; i ++){
myclass my(10-i, i*3);
vect.push_back(my);
}
for(int i = 0 ; i < vect.size(); i ++) cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
sort(vect.begin(), vect.end());
cout<<"after sorted by first:"<<endl;
for(int i = 0 ; i < vect.size(); i ++) cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
cout<<"after sorted by second:"<<endl;
sort(vect.begin(), vect.end(), less_second);
for(int i = 0 ; i < vect.size(); i ++) cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
return 0 ;
}
輸出結果如下:
(10,0) (9,3) (8,6) (7,9) (6,12) (5,15) (4,18) (3,21) (2,24) (1,27)
after sorted by first:
(1,27) (2,24) (3,21) (4,18) (5,15) (6,12) (7,9) (8,6) (9,3) (10,0)
after sorted by second:
(10,0) (9,3) (8,6) (7,9) (6,12) (5,15) (4,18) (3,21) (2,24) (1,27)
你可能會好奇,為什麼有 sort 和 stable_sort、partition 和 stable_partition 之分。差別在於:帶 stable 的函數能保證「相等元素」在排序後的相對次序維持不變。或許你會問,既然相等,還分誰先誰後有意義嗎?這裡要釐清一個觀念:這裡的「相等」,指的是你提供的比較函數判定兩者相等,並不一定是完全一模一樣的元素。
例如,如果你寫了一個比較函數:
bool less_len(const string &str1, const string &str2) {
return str1.length() < str2.length();
}
此時 "apple" 與 "winter" 就是「相等」的(長度相同)。若 "apple" 原本排在 "winter" 前面,用帶 stable 的函數排序後,它們的次序一定不變;若改用不帶 stable 的函數,排序後 "winter" 有可能跑到 "apple" 前面。
全排序即把給定範圍內所有元素依大小關係完整排列。用於全排序的函數原型如下:
template <class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering> void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
template <class RandomAccessIterator> void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering> void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
在第 1、3 種形式中,sort 與 stable_sort 都未指定比較函數,系統預設使用 operator< 對區間 [first,last) 內所有元素排序,因此若你的型別已重載 Operator<,就能省事了。第 2、4 種形式則可自訂比較函數,應用更為靈活。來看實際應用——班上有 10 個學生,我想知道他們的成績排名:
#include <iOStream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
using namespace std;
class student{
public:
student(const string &a, int b):name(a), score(b){}
string name;
int score;
bool Operator < (const student &m)const {
return score< m.score;
}
};
int main() {
vector< student> vect;
student st1("Tom", 74); vect.push_back(st1);
st1.name="Jimy"; st1.score=56; vect.push_back(st1);
st1.name="Mary"; st1.score=92; vect.push_back(st1);
st1.name="Jessy"; st1.score=85; vect.push_back(st1);
st1.name="Jone"; st1.score=56; vect.push_back(st1);
st1.name="Bush"; st1.score=52; vect.push_back(st1);
st1.name="Winter"; st1.score=77; vect.push_back(st1);
st1.name="Andyer"; st1.score=63; vect.push_back(st1);
st1.name="Lily"; st1.score=76; vect.push_back(st1);
st1.name="Maryia"; st1.score=89; vect.push_back(st1);
cout<<"------before sort..."<<endl;
for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
stable_sort(vect.begin(), vect.end(),less<student>());
cout <<"-----after sort ...."<<endl;
for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
return 0 ;
}
輸出如下:
------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Bush: 52
Jimy: 56
Jone: 56
Andyer: 63
Tom: 74
Lily: 76
Winter: 77
Jessy: 85
Maryia: 89
Mary: 92
sort 採用成熟的「快速排序算法」(目前大部分 STL 版本已非單純的快速排序,而是結合內插排序),可保證很好的平均效能,複雜度為 n*log(n)。由於單純快速排序理論上有最差情況(複雜度為 n*n),但目前多數 STL 版本都已做了優化,因此可放心使用。stable_sort 則採用「歸並排序」,在分配足夠記憶體時複雜度為 n*log(n),否則為 n*log(n)*log(n),其優點是保持相等元素排序前後的相對位置不變。
局部排序其實是為了減少不必要的操作而提供的排序方式,函數原型如下:
template <class RandomAccessIterator> void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering> void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, StrictWeakOrdering comp);
template <class InputIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last);
template <class InputIterator, class RandomAccessIterator, class StrictWeakOrdering> RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
理解了 sort 與 stable_sort 後,partial_sort 就不難懂。班上有 10 個學生,我想知道分數最低的 5 名是哪些人。若沒有 partial_sort,你得先用 sort 把所有人排好序再取前 5 個;現在你只需對分數最低 5 名排序,把前面的程式改一行即可:
stable_sort(vect.begin(), vect.end(),less<student>()); 替換為:
partial_sort(vect.begin(), vect.begin()+5, vect.end(),less<student>());
輸出結果為:
------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Bush: 52
Jimy: 56
Jone: 56
Andyer: 63
Tom: 74
Mary: 92
Jessy: 85
Winter: 77
Lily: 76
Maryia: 89
當資料量小時可能看不出優勢,但若是 100 萬個學生要找分數最少的 5 個人,差異就很明顯了。partial_sort 採用堆排序(heapsort),任何情況下複雜度都是 n*log(n)。若你想用 partial_sort 實作全排序,只要讓 middle=last 即可。partial_sort_copy 則是 copy 與 partial_sort 的組合,被排序(複製)的數量取 [first, last) 與 [result_first, result_last) 中較小的那個區間。
nth_element 是個容易看懂卻不易解釋的排序函數,用例子說明會更清楚:班上有 10 個學生,我想知道分數排倒數第 4 名的學生。要滿足這個需求,可以用 sort 排好序後取第 4 位(因為由小到大排),更聰明的做法是用 partial_sort 只排前 4 位。但其實這仍有浪費,因為前兩位根本不必排序,這時就该用 nth_element:
template <class RandomAccessIterator> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, StrictWeakOrdering comp);
針對上述需求,只需把 1.4 的程式改一行:
stable_sort(vect.begin(), vect.end(),less<student>()); 替換為:
nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());
運行結果為:
------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Jone: 56
Bush: 52
Jimy: 56
Andyer: 63
Jessy: 85
Mary: 92
Winter: 77
Tom: 74
Lily: 76
Maryia: 89
第四名是誰?Andyer。為什麼是 begin()+3 而不是 +4?因為 begin() 是第一個,begin()+1 是第二個,依此類推,begin()+3 自然就是第四個了。
這兩個函數嚴格說來並非用於排序,稱之為「分類」算法會更貼切。partition 把一個區間中的元素依某個條件分成兩類,函數原型如下:
template <class ForwardIterator, class Predicate> ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)
template <class ForwardIterator, class Predicate> ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
看看應用:班上 10 個學生,要計算所有沒有及格(低於 60 分)的學生,只需替換 1.4 的程式:
stable_sort(vect.begin(), vect.end(),less<student>()); 替換為:
student exam("pass", 60);
stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));
輸出結果為:
------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Jimy: 56
Jone: 56
Bush: 52
Tom: 74
Mary: 92
Jessy: 85
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
看見了嗎?Jimy、Jone、Bush 都沒有及格。而且因為用的是 stable_partition,元素之間的相對次序沒有改變。
STL 標準容器主要有 vector、list、deque、string、set、multiset、map、multimap,其中 set、multiset、map、multimap 都是以樹結構儲存元素,因此它們中的元素一直是有序的。
這些容器的迭代器類型並不是隨機型迭代器,因此上述那些排序函數對它們是不可用的。上述 sort 函數對下列容器可用:
如果你自訂的容器也支持隨機型迭代器,那麼使用排序算法完全沒問題。對於 list 容器,它自帶一個 sort 成員函數 list::sort(),與算法函數中的 sort 差不多,但 list::sort 是以指標方式排序,也就是所有資料的移動與比較都以指標方式實現,因此排序後的迭代器仍保持有效(vector 中 sort 後的迭代器會失效)。
為什麼要選擇合適的排序函數?或許你並不關心效率,或者你的資料量很小,覺得隨便用哪個函數都無關緊要。其實不然,即使不講效率,選對排序函數也能讓你的程式碼更易讀、更有擴充性,逐漸養成好習慣。
如果你以前用過 C 語言的 qsort,想知道它與上述函數的比較,那我告訴你:qsort 和 sort 一樣,採用的都是快速排序。從效率上看,以下 sort 系列算法由快到慢(耗時由小到大)為:
關於「如何選擇排序函數」,可以參考以下建議:
總之記住一句話:如果你想節約時間,就不要走彎路,也不要走多餘的路!
討論技術就像個無底洞,容易從一點引申出無數技術點,因此需要從全局角度觀察問題,就像觀察 STL 中的 sort 算法一樣。其實 STL 裡還有 make_heap、sort_heap 等排序算法,本文未觸及。本文以實例方式說明了 STL 排序算法的特性,並總結了在實際情況下該如何選擇合適的算法。

條款31:如何選擇排序函數
The Standard Librarian: Sorting in the Standard Library
Effective STL 中文版
Standard Template Library Programmer's Guide