c++非變易算法-stl算法
C++ STL標準模板庫在數(shù)據(jù)結(jié)構和算法的實踐領域發(fā)揮著重要作用，極大的提高了開發(fā)效率。STL的三大組成部分為容器、迭代器、算法，本文主要講解STL算法中的非變易算法。本文從實踐的角度簡單介紹了一下相關函數(shù)的使用。
C++ STL的非變易算法（Non-mutating algorithms）是一組不破壞函數(shù)數(shù)據(jù)的模板函數(shù)，用來對序列數(shù)據(jù)進行逐個處理、元素查找、子序列搜索、統(tǒng)計和匹配，基本上可用于各種容器。下面的敘述中迭代器區(qū)間默認為[first, last)，迭代器具有“++”迭代和“*”訪問操作。
逐個處理算法
for_each函數(shù)
該函數(shù)對迭代器區(qū)間的每個元素，執(zhí)行單參數(shù)函數(shù)對象定義的操作。
下面的實例程序，將打印容器vector中的每個元素。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void print(int x) {
cout << x << " ";
}
int main(void) {
vector<int> v;
for(int i = 0; i < 10; i++) {
v.push_back(i * 2);
}
for_each(v.begin(), v.end(), print);
return 0;
}
結(jié)果輸出為：
0 2 4 6 8 10 12 14 16 18
元素查找算法
find函數(shù)
該函數(shù)用于查找等于某值的元素。如果迭代器i所指的元素滿足*i == value，則返回迭代器i。未找到滿足條件的元素，返回last。只要找到第一個滿足條件的元素就返回迭代器位置，不再繼續(xù)查找。
下面的示例程序查找容器vector中，第一個值為6的元素，打印元素位置及其前一元素。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
vector<int> v;
for(int i = 0; i < 10; i++) {
v.push_back(i * 2);
}
vector<int>::iterator iv = find(v.begin(), v.end(), 6);
if(iv == v.end()) {
cout << "Find nothing." << endl;
} else {
cout << "The postion of " << *iv << " is " << iv - v.begin() << endl;
cout << "The previous element of it is " << *(--iv) << endl;
}
return 0;
}
結(jié)果輸出為：
The postion of 6 is 3
The previous element of it is 4
find_if函數(shù)
該函數(shù)是find的一個謂詞判斷版本，查找滿足謂詞判斷函數(shù)的元素。
下面的實例程序?qū)ふ胰萜鱲ector中第一個能被3整除的元素。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int divBy3(int x) {
return x % 3 ? 0 : 1;
}
int main(void) {
vector<int> v;
for(int i = 1; i < 10; i++) {
v.push_back(i * 2);
}
vector<int>::iterator iv = find_if(v.begin(), v.end(), divBy3);
if(iv == v.end()) {
cout << "None could be divided by 3 with no remaineder." << endl;
} else {
cout << *iv << " could be divided by 3 with no remainder." << endl;
}
return 0;
}
結(jié)果輸出為：
6 could be divided by 3 with no remainder.
adjacent_find函數(shù)
該函數(shù)用于查找相等或滿足條件的鄰近元素對。它有兩個使用原型，一個用于查找相等的兩個連續(xù)元素，另一個使用二元謂詞判斷，查找滿足條件的鄰近元素對。
下面的實例程序用于尋找容器中相等的元素和奇偶性相同的元素。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int parity_equal(int x, int y) {
return (x - y) % 2 == 0 ? 1 : 0;
}
int main(void) {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(5);
v.push_back(5);
v.push_back(7);
vector<int>::iterator iv = adjacent_find(v.begin(), v.end());
if(iv != v.end()) {
cout << "There are two equal elements." << endl;
cout << "It is " << *iv << endl;
}
iv = adjacent_find(v.begin(), v.end(), parity_equal);
if(iv != v.end()) {
cout << "There are two parity euqal elements." << endl;
cout << "They are " << *iv << " and ";
iv++;
cout << *iv << endl;
}
return 0;
}
輸出結(jié)果為：
There are two equal elements.
It is 5
There are two parity euqal elements.
They are 3 and 5
find_first_of函數(shù)
該函數(shù)用于查找某個范圍之內(nèi)的元素。它有兩個使用原型，一個是相等，另一個是二元謂詞判斷。元素找到則返回迭代器，否則返回末位置。
下面的實例程序用于計算容器v2中元素在容器v中重合出現(xiàn)的首位置。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(5);
v.push_back(5);
v.push_back(7);
vector<int> v2;
v2.push_back(3);
v2.push_back(3);
v2.push_back(5);
vector<int>::iterator iv = find_first_of(v.begin(), v.end(), v2.begin(), v2.end());
cout << "The position of the first equal element is " << iv - v.begin() << endl;
return 0;
}
輸出結(jié)果為：
The position of the first equal element is 3
元素統(tǒng)計算法
count函數(shù)
該函數(shù)用于計算容器中某個給定值的出現(xiàn)次數(shù)。它有兩個使用原型，區(qū)別在于計數(shù)是直接返回還是引用返回。
下面的實例程序計算了容器中5的出現(xiàn)次數(shù)，結(jié)果直接返回。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
vector<int> v;
for(int i = 0; i < 17; i++) {
v.push_back(i % 6);
}
int num = count(v.begin(), v.end(), 5);
cout << "The number of 5 is " << num << endl;
return 0;
}
輸出結(jié)果為：
The number of 5 is 2
count_if函數(shù)
該函數(shù)使用謂詞判斷函數(shù)，統(tǒng)計迭代器區(qū)間上滿足條件的元素個數(shù)。它有兩個使用原型，區(qū)別在與計數(shù)是直接返回還是引用返回。
下面的實例程序統(tǒng)計了容器中大于10的數(shù)字的出現(xiàn)次數(shù)，結(jié)果直接返回。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int greaterThan10(int x) {
return x > 10 ? 1 : 0;
}
int main(void) {
vector<int> v;
for(int i = 0; i < 17; i++) {
v.push_back(i);
}
int num = count_if(v.begin(), v.end(), greaterThan10);
cout << "The number of the figure that greater than 10 is " << num << endl;
return 0;
}
輸出結(jié)果為：
The number of the figure that greater than 10 is 6
序列匹配算法
mismatch函數(shù)
該函數(shù)用于比較兩個序列，找出首個不匹配元素的位置。它有兩個使用原型，分別為不相等和不滿足二元謂詞條件。
該函數(shù)還涉及到pair的使用。
下面的實例程序比較兩個整型容器，并找出不匹配的數(shù)字。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
vector<int> v1, v2;
v1.push_back(3);
v1.push_back(5);
v1.push_back(5);
v2.push_back(3);
v2.push_back(5);
v2.push_back(7);
pair<vector<int>::iterator, vector<int>::iterator> result = mismatch(v1.begin(), v1.end(), v2.begin());
if(result.first == v1.end() && result.second == v2.end()) {
cout << "v1 is same as v2." << endl;
} else {
cout << "The dismatching figure are "
<< *(result.first) << " and "
<< *(result.second) << endl;
}
return 0;
}
輸出結(jié)果為：
The dismatching figure are 5 and 7
equal函數(shù)
該函數(shù)逐一比較兩個序列的元素是否相等，返回值為true/false，不返回迭代器值。它有兩個使用原型，分別為元素相等和二元謂詞判斷條件。
下面的實例程序用于比較兩容器中數(shù)字絕對值是否相等。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int absEqual(int x, int y) {
//return (x == abs(y) || y == abs(x)) ? 1 : 0;
return abs(x) == abs(y) ? 1 : 0;
}
int main(void) {
vector<int> v1, v2;
v1.push_back(3);
v1.push_back(5);
v1.push_back(5);
v2.push_back(3);
v2.push_back(5);
v2.push_back(-5);
if(equal(v1.begin(), v1.end(), v2.begin(), absEqual)) {
cout << "The elements of v1 and v2 are equal in abosolute value." << endl;
} else {
cout << "The elements of v1 and v2 are not equal in abosolute value." << endl;
}
return 0;
}
輸出結(jié)果為：
The elements of v1 and v2 are equal in abosolute value.
子序列搜索算法
search函數(shù)
該函數(shù)在一個序列中搜索與另一序列匹配的子序列。它有兩個使用原型，分別為完全匹配和二元謂詞判斷。匹配成功則返回子序列的首個元素的迭代器值。
search函數(shù)與find_first_of函數(shù)形似，但不相同。search找的是一塊相同的區(qū)域，要求這塊區(qū)域與后面列表的元素及其順序相同；find_first_of找的是一個元素，只要這個元素是后面一個列表的任意一個就行。
下面的實例程序說明了search與find_first_of的不同。
#include <iostream>
#include <algorithm>
#include <vector>
int main(void) {
vector<int> v1, v2;
v1.push_back(1);
v1.push_back(4);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v2.push_back(2);
v2.push_back(3);
v2.push_back(4);
vector<int>::iterator ivSearch, ivFind;
ivSearch = search(v1.begin(), v1.end(), v2.begin(), v2.end());
ivFind = find_first_of(v1.begin(), v1.end(), v2.begin(), v2.end());
cout << "Position of search: " << ivSearch - v1.begin() << endl;
cout << "Position of find_first_of: " << ivFind - v1.begin() << endl;
return 0;
}
輸出結(jié)果為：
Position of search: 2
Position of find_first_of: 1
search_n函數(shù)
該函數(shù)用于搜索序列中是否有一系列元素值均為某個給定值的子序列。它有兩個使用原型，分別為值相等和滿足謂詞判斷條件。
下面的實例程序展示了尋找3個連續(xù)的數(shù)字8的過程。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
vector<int> v;
v.push_back(3);
v.push_back(8);
v.push_back(8);
v.push_back(8);
v.push_back(4);
vector<int>::iterator iv = search_n(v.begin(), v.end(), 3, 8);
if(iv == v.end()) {
cout << "There are no three consecutive 8." << endl;
} else {
cout << "Three consecutive 8 is founded." << endl;
}
return 0;
}
結(jié)果輸出為：
Three consecutive 8 is founded.
find_end函數(shù)
該函數(shù)用于在一個序列中搜索出最后一個與另一序列匹配的子序列。用search函數(shù)作用相似，方向相反。
下面的實例程序，展示了搜索容器v中最后一個與v1匹配的子序列的過程。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
vector<int> v, v2;
v.push_back(1);
v.push_back(3);
v.push_back(5);
v.push_back(3);
v.push_back(5);
v.push_back(7);
v2.push_back(3);
v2.push_back(5);
vector<int>::iterator iv = find_end(v.begin(), v.end(), v2.begin(), v2.end());
if(iv != v.end()) {
cout << "The position of last matching subsequence is " << iv - v.begin() << endl;
}
return 0;
}
輸出結(jié)果為：
The position of last matching subsequence is 3
您可能感興趣的文章
- 04-02c語言沒有round函數(shù) round c語言
- 01-10深入理解C++中常見的關鍵字含義
- 01-10使用C++實現(xiàn)全排列算法的方法詳解
- 01-10c++中inline的用法分析
- 01-10深入理解二叉樹的非遞歸遍歷
- 01-10用C++實現(xiàn)DBSCAN聚類算法
- 01-10全排列算法的非遞歸實現(xiàn)與遞歸實現(xiàn)的方法(C++)
- 01-10C++大數(shù)模板(推薦)
- 01-10淺談C/C++中的static與extern關鍵字的使用詳解
- 01-10深入C/C++浮點數(shù)在內(nèi)存中的存儲方式詳解
閱讀排行
本欄相關
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言的正則匹配函數(shù) c語言正則表達
- 04-02c語言用函數(shù)寫分段 用c語言表示分段
- 04-02c語言中對數(shù)函數(shù)的表達式 c語言中對
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段
- 04-02C語言中怎么打出三角函數(shù) c語言中怎
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求
隨機閱讀
- 01-10delphi制作wav文件的方法
- 04-02jquery與jsp,用jquery
- 08-05dedecms(織夢)副欄目數(shù)量限制代碼修改
- 08-05DEDE織夢data目錄下的sessions文件夾有什
- 01-11ajax實現(xiàn)頁面的局部加載
- 01-11Mac OSX 打開原生自帶讀寫NTFS功能(圖文
- 01-10使用C語言求解撲克牌的順子及n個骰子
- 01-10SublimeText編譯C開發(fā)環(huán)境設置
- 01-10C#中split用法實例總結(jié)
- 08-05織夢dedecms什么時候用欄目交叉功能？