原創(chuàng )：非變易算法 - STL算法
作者：MilkCu
摘要：C++ STL標準模板庫在數據結構和算法的實(shí)踐領(lǐng)域發(fā)揮著(zhù)重要作用，極大的提高了開(kāi)發(fā)效率。STL的三大組成部分為容器、迭代器、算法，本文主要講解STL算法中的非變易算法。本文從實(shí)踐的角度簡(jiǎn)單介紹了一下相關(guān)函數的使用。
引言
C++ STL的非變易算法（Non-mutating algorithms）是一組不破壞函數數據的模板函數，用來(lái)對序列數據進(jìn)行逐個(gè)處理、元素查找、子序列搜索、統計和匹配，基本上可用于各種容器。下面的敘述中迭代器區間默認為[first, last)，迭代器具有“++”迭代和“*”訪(fǎng)問(wèn)操作。
逐個(gè)處理算法
for_each函數
該函數對迭代器區間的每個(gè)元素，執行單參數函數對象定義的操作。
下面的實(shí)例程序，將打印容器vector中的每個(gè)元素。
10 | for(int i = 0; i < 10; i++) { |
13 | for_each(v.begin(), v.end(), print); |
結果輸出為：
0 2 4 6 8 10 12 14 16 18
元素查找算法
find函數
該函數用于查找等于某值的元素。如果迭代器i所指的元素滿(mǎn)足*i == value，則返回迭代器i。未找到滿(mǎn)足條件的元素，返回last。只要找到第一個(gè)滿(mǎn)足條件的元素就返回迭代器位置，不再繼續查找。
下面的示例程序查找容器vector中，第一個(gè)值為6的元素，打印元素位置及其前一元素。
07 | for(int i = 0; i < 10; i++) { |
10 | vector<int>::iterator iv = find(v.begin(), v.end(), 6); |
12 | cout << "Find nothing." << endl; |
14 | cout << "The postion of " << *iv << " is " << iv - v.begin() << endl; |
15 | cout << "The previous element of it is " << *(--iv) << endl; |
結果輸出為：
The postion of 6 is 3
The previous element of it is 4
find_if函數
該函數是find的一個(gè)謂詞判斷版本，查找滿(mǎn)足謂詞判斷函數的元素。
下面的實(shí)例程序將尋找容器vector中第一個(gè)能被3整除的元素。
10 | for(int i = 1; i < 10; i++) { |
13 | vector<int>::iterator iv = find_if(v.begin(), v.end(), divBy3); |
15 | cout << "None could be divided by 3 with no remaineder." << endl; |
17 | cout << *iv << " could be divided by 3 with no remainder." << endl; |
結果輸出為：
6 could be divided by 3 with no remainder.
adjacent_find函數
該函數用于查找相等或滿(mǎn)足條件的鄰近元素對。它有兩個(gè)使用原型，一個(gè)用于查找相等的兩個(gè)連續元素，另一個(gè)使用二元謂詞判斷，查找滿(mǎn)足條件的鄰近元素對。
下面的實(shí)例程序用于尋找容器中相等的元素和奇偶性相同的元素。
05 | int parity_equal(int x, int y) { |
06 | return (x - y) % 2 == 0 ? 1 : 0; |
16 | vector<int>::iterator iv = adjacent_find(v.begin(), v.end()); |
18 | cout << "There are two equal elements." << endl; |
19 | cout << "It is " << *iv << endl; |
21 | iv = adjacent_find(v.begin(), v.end(), parity_equal); |
23 | cout << "There are two parity euqal elements." << endl; |
24 | cout << "They are " << *iv << " and "; |
輸出結果為：
There are two equal elements.
It is 5
There are two parity euqal elements.
They are 3 and 5
find_first_of函數
該函數用于查找某個(gè)范圍之內的元素。它有兩個(gè)使用原型，一個(gè)是相等，另一個(gè)是二元謂詞判斷。元素找到則返回迭代器，否則返回末位置。
下面的實(shí)例程序用于計算容器v2中元素在容器v中重合出現的首位置。
18 | vector<int>::iterator iv = find_first_of(v.begin(), v.end(), v2.begin(), v2.end()); |
19 | cout << "The position of the first equal element is " << iv - v.begin() << endl; |
輸出結果為：
The position of the first equal element is 3
元素統計算法
count函數
該函數用于計算容器中某個(gè)給定值的出現次數。它有兩個(gè)使用原型，區別在于計數是直接返回還是引用返回。
下面的實(shí)例程序計算了容器中5的出現次數，結果直接返回。
07 | for(int i = 0; i < 17; i++) { |
10 | int num = count(v.begin(), v.end(), 5); |
11 | cout << "The number of 5 is " << num << endl; |
輸出結果為：
The number of 5 is 2
count_if函數
該函數使用謂詞判斷函數，統計迭代器區間上滿(mǎn)足條件的元素個(gè)數。它有兩個(gè)使用原型，區別在與計數是直接返回還是引用返回。
下面的實(shí)例程序統計了容器中大于10的數字的出現次數，結果直接返回。
05 | int greaterThan10(int x) { |
06 | return x > 10 ? 1 : 0; |
10 | for(int i = 0; i < 17; i++) { |
13 | int num = count_if(v.begin(), v.end(), greaterThan10); |
14 | cout << "The number of the figure that greater than 10 is " << num << endl; |
輸出結果為：
The number of the figure that greater than 10 is 6
序列匹配算法
mismatch函數
該函數用于比較兩個(gè)序列，找出首個(gè)不匹配元素的位置。它有兩個(gè)使用原型，分別為不相等和不滿(mǎn)足二元謂詞條件。
該函數還涉及到pair的使用。
下面的實(shí)例程序比較兩個(gè)整型容器，并找出不匹配的數字。
13 | pair<vector<int>::iterator, vector<int>::iterator> result = mismatch(v1.begin(), v1.end(), v2.begin()); |
14 | if(result.first == v1.end() && result.second == v2.end()) { |
15 | cout << "v1 is same as v2." << endl; |
17 | cout << "The dismatching figure are " |
18 | << *(result.first) << " and " |
19 | << *(result.second) << endl; |
輸出結果為：
The dismatching figure are 5 and 7
equal函數
該函數逐一比較兩個(gè)序列的元素是否相等，返回值為true/false，不返回迭代器值。它有兩個(gè)使用原型，分別為元素相等和二元謂詞判斷條件。
下面的實(shí)例程序用于比較兩容器中數字絕對值是否相等。
05 | int absEqual(int x, int y) { |
06 | //return (x == abs(y) || y == abs(x)) ? 1 : 0; |
07 | return abs(x) == abs(y) ? 1 : 0; |
17 | if(equal(v1.begin(), v1.end(), v2.begin(), absEqual)) { |
18 | cout << "The elements of v1 and v2 are equal in abosolute value." << endl; |
20 | cout << "The elements of v1 and v2 are not equal in abosolute value." << endl; |
輸出結果為：
The elements of v1 and v2 are equal in abosolute value.
子序列搜索算法
search函數
該函數在一個(gè)序列中搜索與另一序列匹配的子序列。它有兩個(gè)使用原型，分別為完全匹配和二元謂詞判斷。匹配成功則返回子序列的首個(gè)元素的迭代器值。
search函數與find_first_of函數形似，但不相同。search找的是一塊相同的區域，要求這塊區域與后面列表的元素及其順序相同；find_first_of找的是一個(gè)元素，只要這個(gè)元素是后面一個(gè)列表的任意一個(gè)就行。
下面的實(shí)例程序說(shuō)明了search與find_first_of的不同。
14 | vector<int>::iterator ivSearch, ivFind; |
15 | ivSearch = search(v1.begin(), v1.end(), v2.begin(), v2.end()); |
16 | ivFind = find_first_of(v1.begin(), v1.end(), v2.begin(), v2.end()); |
17 | cout << "Position of search: " << ivSearch - v1.begin() << endl; |
18 | cout << "Position of find_first_of: " << ivFind - v1.begin() << endl; |
輸出結果為：
Position of search: 2
Position of find_first_of: 1
search_n函數
該函數用于搜索序列中是否有一系列元素值均為某個(gè)給定值的子序列。它有兩個(gè)使用原型，分別為值相等和滿(mǎn)足謂詞判斷條件。
下面的實(shí)例程序展示了尋找3個(gè)連續的數字8的過(guò)程。
12 | vector<int>::iterator iv = search_n(v.begin(), v.end(), 3, 8); |
14 | cout << "There are no three consecutive 8." << endl; |
16 | cout << "Three consecutive 8 is founded." << endl; |
結果輸出為：
Three consecutive 8 is founded.
find_end函數
該函數用于在一個(gè)序列中搜索出最后一個(gè)與另一序列匹配的子序列。用search函數作用相似，方向相反。
下面的實(shí)例程序，展示了搜索容器v中最后一個(gè)與v1匹配的子序列的過(guò)程。
15 | vector<int>::iterator iv = find_end(v.begin(), v.end(), v2.begin(), v2.end()); |
17 | cout << "The position of last matching subsequence is " << iv - v.begin() << endl; |
輸出結果為：
The position of last matching subsequence is 3
小結
本文主要介紹了C++ STL算法庫中的非變易算法，是一些原則上不會(huì )變更操作數據的算法，包括：
- 元素搜索算法：find, find_if, adjacent_find, find_first_of
- 子序列搜索算法：search, search_n, find_end
這些函數均包含于<algorithm>頭文件，本文給出的所有代碼在VS2010中編譯運行通過(guò)。
參考
[1] http://www.cplusplus.com/reference/algorithm/, <algorithm> - C++ Reference;
[2] C++ STL開(kāi)發(fā)技術(shù)導引, 葉志軍, 人民郵電出版社.
（全文完）
