0 前言: STL，為什么你必須掌握
對(duì)于程序員來說，數(shù)據(jù)結(jié)構(gòu)是必修的一門課。從查找到排序，從鏈表到二叉樹，幾乎所有的算法和原理都需要理解，理解不了也要死記硬背下來。幸運(yùn)的是這些理論都已經(jīng)比較成熟，算法也基本固定下來，不需要你再去花費(fèi)心思去考慮其算法原理，也不用再去驗(yàn)證其準(zhǔn)確性。不過，等你開始應(yīng)用計(jì)算機(jī)語言來工作的時(shí)候，你會(huì)發(fā)現(xiàn)，面對(duì)不同的需求你需要一次又一次去用代碼重復(fù)實(shí)現(xiàn)這些已經(jīng)成熟的算法，而且會(huì)一次又一次陷入一些由于自己疏忽而產(chǎn)生的bug中。這時(shí)，你想找一種工具，已經(jīng)幫你實(shí)現(xiàn)這些功能，你想怎么用就怎么用，同時(shí)不影響性能。你需要的就是STL, 標(biāo)準(zhǔn)模板庫！
西方有句諺語：不要重復(fù)發(fā)明輪子！
STL幾乎封裝了所有的數(shù)據(jù)結(jié)構(gòu)中的算法，從鏈表到隊(duì)列，從向量到堆棧，對(duì)hash到二叉樹，從搜索到排序，從增加到刪除......可以說，如果你理解了STL，你會(huì)發(fā)現(xiàn)你已不用拘泥于算法本身，從而站在巨人的肩膀上去考慮更高級(jí)的應(yīng)用。
排序是最廣泛的算法之一，本文詳細(xì)介紹了STL中不同排序算法的用法和區(qū)別。
1 STL提供的Sort 算法
C++之所以得到這么多人的喜歡，是因?yàn)樗染哂忻嫦驅(qū)ο蟮母拍睿直３至薈語言高效的特點(diǎn)。STL 排序算法同樣需要保持高效。因此，對(duì)于不同的需求，STL提供的不同的函數(shù)，不同的函數(shù)，實(shí)現(xiàn)的算法又不盡相同。
1.1 所有sort算法介紹
所有的sort算法的參數(shù)都需要輸入一個(gè)范圍，[begin, end)。這里使用的迭代器(iterator)都需是隨機(jī)迭代器(RadomAccessIterator), 也就是說可以隨機(jī)訪問的迭代器，如：it+n什么的。（partition 和stable_partition 除外）
如果你需要自己定義比較函數(shù)，你可以把你定義好的仿函數(shù)(functor)作為參數(shù)傳入。每種算法都支持傳入比較函數(shù)。以下是所有STL sort算法函數(shù)的名字列表:
| 函數(shù)名 |
功能描述 |
| sort |
對(duì)給定區(qū)間所有元素進(jìn)行排序 |
| stable_sort |
對(duì)給定區(qū)間所有元素進(jìn)行穩(wěn)定排序 |
| partial_sort |
對(duì)給定區(qū)間所有元素部分排序 |
| partial_sort_copy |
對(duì)給定區(qū)間復(fù)制并排序 |
| nth_element |
找出給定區(qū)間的某個(gè)位置對(duì)應(yīng)的元素 |
| is_sorted |
判斷一個(gè)區(qū)間是否已經(jīng)排好序 |
| partition |
使得符合某個(gè)條件的元素放在前面 |
| stable_partition |
相對(duì)穩(wěn)定的使得符合某個(gè)條件的元素放在前面 |
其中nth_element 是最不易理解的，實(shí)際上，這個(gè)函數(shù)是用來找出第幾個(gè)。例如：找出包含7個(gè)元素的數(shù)組中排在中間那個(gè)數(shù)的值，此時(shí)，我可能不關(guān)心前面，也不關(guān)心后面，我只關(guān)心排在第四位的元素值是多少。
1.2 sort 中的比較函數(shù)
當(dāng)你需要按照某種特定方式進(jìn)行排序時(shí)，你需要給sort指定比較函數(shù)，否則程序會(huì)自動(dòng)提供給你一個(gè)比較函數(shù)。
1
vector < int > vect;
2//
3sort(vect.begin(), vect.end());
4//此時(shí)相當(dāng)于調(diào)用
5sort(vect.begin(), vect.end(), less<int>() );上述例子中系統(tǒng)自己為sort提供了less仿函數(shù)。在STL中還提供了其他仿函數(shù)，以下是仿函數(shù)列表:
| 名稱 |
功能描述 |
| equal_to |
相等 |
| not_equal_to |
不相等 |
| less |
小于 |
| greater |
大于 |
| less_equal |
小于等于 |
| greater_equal |
大于等于 |
需要注意的是，這些函數(shù)不是都能適用于你的sort算法，如何選擇，決定于你的應(yīng)用。另外，不能直接寫入仿函數(shù)的名字，而是要寫其重載的()函數(shù)：
less<int>()
greater<int>()
當(dāng)你的容器中元素時(shí)一些標(biāo)準(zhǔn)類型（int float char)或者string時(shí)，你可以直接使用這些函數(shù)模板。但如果你時(shí)自己定義的類型或者你需要按照其他方式排序，你可以有兩種方法來達(dá)到效果：一種是自己寫比較函數(shù)。另一種是重載類型的'<'操作賦。
1#include <iostream>
2#include <algorithm>
3#include <functional>
4#include <vector>
5using namespace std;
6
7class myclass {
8 public:
9 myclass(int a, int b):first(a), second(b){}
10 int first;
11 int second;
12 bool operator < (const myclass &m)const {
13 return first < m.first;
14 }
15};
16
17bool less_second(const myclass & m1, const myclass & m2) {
18 return m1.second < m2.second;
19}
20
21int main() {
22
23 vector< myclass > vect;
24 for(int i = 0 ; i < 10 ; i ++){
25 myclass my(10-i, i*3);
26 vect.push_back(my);
27 }
28 for(int i = 0 ; i < vect.size(); i ++)
29 cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
30 sort(vect.begin(), vect.end());
31 cout<<"after sorted by first:"<<endl;
32 for(int i = 0 ; i < vect.size(); i ++)
33 cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
34 cout<<"after sorted by second:"<<endl;
35 sort(vect.begin(), vect.end
知道其輸出結(jié)果是什么了吧：
(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)
1.3 sort 的穩(wěn)定性
你發(fā)現(xiàn)有sort和stable_sort，還有 partition 和stable_partition， 感到奇怪吧。其中的區(qū)別是，帶有stable的函數(shù)可保證相等元素的原本相對(duì)次序在排序后保持不變。或許你會(huì)問，既然相等，你還管他相對(duì)位置呢，也分不清楚誰是誰了？這里需要弄清楚一個(gè)問題，這里的相等，是指你提供的函數(shù)表示兩個(gè)元素相等，并不一定是一摸一樣的元素。
例如，如果你寫一個(gè)比較函數(shù):
1bool less_len(const string &str1, const string &str2)
2{
3 return str1.length() < str2.length();
4}此時(shí)，"apple" 和 "winter" 就是相等的，如果在"apple" 出現(xiàn)在"winter"前面，用帶stable的函數(shù)排序后，他們的次序一定不變，如果你使用的是不帶"stable"的函數(shù)排序，那么排序完后，"Winter"有可能在"apple"的前面。
1.4 全排序
全排序即把所給定范圍所有的元素按照大小關(guān)系順序排列。用于全排序的函數(shù)有
1template <class RandomAccessIterator>
2void sort(RandomAccessIterator first, RandomAccessIterator last);
3
4template <class RandomAccessIterator, class StrictWeakOrdering>
5void sort(RandomAccessIterator first, RandomAccessIterator last,
6StrictWeakOrdering comp);
7
8template <class RandomAccessIterator>
9void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
10
11template <class RandomAccessIterator, class StrictWeakOrdering>
12void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
13StrictWeakOrdering comp);
在第1，3種形式中，sort 和 stable_sort都沒有指定比較函數(shù)，系統(tǒng)會(huì)默認(rèn)使用operator< 對(duì)區(qū)間[first,last)內(nèi)的所有元素進(jìn)行排序, 因此，如果你使用的類型義軍已經(jīng)重載了operator<函數(shù)，那么你可以省心了。第2, 4種形式，你可以隨意指定比較函數(shù)，應(yīng)用更為靈活一些。來看看實(shí)際應(yīng)用：
班上有10個(gè)學(xué)生，我想知道他們的成績(jī)排名。
1#include <iostream>
2#include <algorithm>
3#include <functional>
4#include <vector>
5#include <string>
6using namespace std;
7
8class student{
9 public:
10 student(const string &a, int b):name(a), score(b){}
11 string name;
12 int score;
13 bool operator < (const student &m)const {
14 return score< m.score;
15 }
16};
17
18int main() {
19 vector< student> vect;
20 student st1("Tom", 74);
21 vect.push_back(st1);
22 st1.name="Jimy";
23 st1.score=56;
24 vect.push_back(st1);
25 st1.name="Mary";
26 st1.score=92;
27 vect.push_back(st1);
28 st1.name="Jessy";
29 st1.score=85;
30 vect.push_back(st1);
31 st1.name="Jone";
32 st1.score=56;
33 vect.push_back(st1);
34 st1.name="Bush";
35 st1.score=52;
36 vect.push_back(st1);
37 st1.name="Winter";
38 st1.score=77;
39 vect.push_back(st1);
40 st1.name="Andyer";
41 st1.score=63;
42 vect.push_back(st1);
43 st1.name="Lily";
44 st1.score=76;
45 vect.push_back(st1);
46 st1.name="Maryia";
47 st1.score=89;
48 vect.push_back(st1);
49 cout<<"------before sort"<<endl;
50 for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
51 stable_sort(vect.begin(), vect.end(),less<student>());
52 cout <<"-----after sort ."<<endl;
53 for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
54 return 0 ;
55}