程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 非變易算法

非變易算法

編輯：C++入門知識

原創：非變易算法 - STL算法

作者：MilkCu

摘要：C++ STL標准模板庫在數據結構和算法的實踐領域發揮著重要作用，極大的提高了開發效率。STL的三大組成部分為容器、迭代器、算法，本文主要講解STL算法中的非變易算法。本文從實踐的角度簡單介紹了一下相關函數的使用。

引言

C++ STL的非變易算法（Non-mutating algorithms）是一組不破壞函數數據的模板函數，用來對序列數據進行逐個處理、元素查找、子序列搜索、統計和匹配，基本上可用於各種容器。下面的敘述中迭代器區間默認為[first, last)，迭代器具有“++”迭代和“*”訪問操作。

逐個處理算法

for_each函數

該函數對迭代器區間的每個元素，執行單參數函數對象定義的操作。

下面的實例程序，將打印容器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;
}

結果輸出為：

0 2 4 6 8 10 12 14 16 18

元素查找算法

find函數

該函數用於查找等於某值的元素。如果迭代器i所指的元素滿足*i == value，則返回迭代器i。未找到滿足條件的元素，返回last。只要找到第一個滿足條件的元素就返回迭代器位置，不再繼續查找。

下面的示例程序查找容器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;
}

結果輸出為：

The postion of 6 is 3
The previous element of it is 4

find_if函數

該函數是find的一個謂詞判斷版本，查找滿足謂詞判斷函數的元素。

下面的實例程序將尋找容器vector中第一個能被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;
}

結果輸出為：

6 could be divided by 3 with no remainder.

adjacent_find函數

該函數用於查找相等或滿足條件的鄰近元素對。它有兩個使用原型，一個用於查找相等的兩個連續元素，另一個使用二元謂詞判斷，查找滿足條件的鄰近元素對。

下面的實例程序用於尋找容器中相等的元素和奇偶性相同的元素。

#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;
}

輸出結果為：

There are two equal elements.
It is 5
There are two parity euqal elements.
They are 3 and 5

find_first_of函數

該函數用於查找某個范圍之內的元素。它有兩個使用原型，一個是相等，另一個是二元謂詞判斷。元素找到則返回迭代器，否則返回末位置。

下面的實例程序用於計算容器v2中元素在容器v中重合出現的首位置。 

#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;
}

輸出結果為：

The position of the first equal element is 3

元素統計算法

count函數

該函數用於計算容器中某個給定值的出現次數。它有兩個使用原型，區別在於計數是直接返回還是引用返回。

下面的實例程序計算了容器中5的出現次數，結果直接返回。

#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;
}

輸出結果為：

The number of 5 is 2

count_if函數

該函數使用謂詞判斷函數，統計迭代器區間上滿足條件的元素個數。它有兩個使用原型，區別在與計數是直接返回還是引用返回。

下面的實例程序統計了容器中大於10的數字的出現次數，結果直接返回。

#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;
}

輸出結果為：

The number of the figure that greater than 10 is 6

序列匹配算法

mismatch函數

該函數用於比較兩個序列，找出首個不匹配元素的位置。它有兩個使用原型，分別為不相等和不滿足二元謂詞條件。

該函數還涉及到pair的使用。

下面的實例程序比較兩個整型容器，並找出不匹配的數字。

#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;
}

輸出結果為：

The dismatching figure are 5 and 7

equal函數

該函數逐一比較兩個序列的元素是否相等，返回值為true/false，不返回迭代器值。它有兩個使用原型，分別為元素相等和二元謂詞判斷條件。

下面的實例程序用於比較兩容器中數字絕對值是否相等。

#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;
}

輸出結果為：

The elements of v1 and v2 are equal in abosolute value.

子序列搜索算法

search函數

該函數在一個序列中搜索與另一序列匹配的子序列。它有兩個使用原型，分別為完全匹配和二元謂詞判斷。匹配成功則返回子序列的首個元素的迭代器值。

search函數與find_first_of函數形似，但不相同。search找的是一塊相同的區域，要求這塊區域與後面列表的元素及其順序相同；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;
}

輸出結果為：

Position of search: 2
Position of find_first_of: 1

search_n函數

該函數用於搜索序列中是否有一系列元素值均為某個給定值的子序列。它有兩個使用原型，分別為值相等和滿足謂詞判斷條件。

下面的實例程序展示了尋找3個連續的數字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;
}

結果輸出為：

Three consecutive 8 is founded.

find_end函數

該函數用於在一個序列中搜索出最後一個與另一序列匹配的子序列。用search函數作用相似，方向相反。

下面的實例程序，展示了搜索容器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;
}

輸出結果為：

The position of last matching subsequence is 3

小結

本文主要介紹了C++ STL算法庫中的非變易算法，是一些原則上不會變更操作數據的算法，包括：

  • 逐個查找算法：for_each
  • 元素搜索算法：find, find_if, adjacent_find, find_first_of
  • 元素統計算法：count, count_if
  • 序列匹配算法：mismatch, equal
  • 子序列搜索算法：search, search_n, find_end

這些函數均包含於<algorithm>頭文件，本文給出的所有代碼在VS2010中編譯運行通過。

參考

[1] http://www.cplusplus.com/reference/algorithm/, <algorithm> - C++ Reference;

[2] C++ STL開發技術導引, 葉志軍, 人民郵電出版社.

（全文完）

  1. 上一頁:
  2. 下一頁:
C++入門知識
Linux C++的多線程編程，linux多線程編程

Linux C++的多線程編程，linux多線程編程1. 引
SpringMVC+Spring+Mybatis整合

SpringMVC+Spring+Mybatis整合 創
0-1背包問題，0-1背包

0-1背包問題，0-1背包問題： 有N件物品和一個容量為V的
Copy List with Random Pointer

題目原型： A linked list is gi
QT的QWebView顯示網頁不全，qtqwebview不全

QT的QWebView顯示網頁不全，qtqwebview不全
NYOJ：題目529 flip，nyoj題目529flip

NYOJ：題目529 flip，nyoj題目529flip題
相關文章
    没有相关文章
閱讀排行榜
HDU1520:Anniversary party(樹形DP) 對於void類型深層探索 QSettings的簡單操作 為什麼多線程讀寫 shared_ptr 要加鎖？ （轉）學習C++ 快速冪取模_C++，冪取模_C Effective C++ 第二版 1)const和inline 2)iostream POJ 3321 Apple Tree POJ 2769 Reduced ID Numbers 同余定理 Yes or No：21天教你學會C++ bzoj2287【POJ Challenge】消失之物
熱門圖文
php函數索引1 cin標准輸入流詳解，cin輸入流詳解 Http_Referer,Server_Name和Http_Host C# 動態編譯、動態執行、動態調試 加密-JS修改密碼，在修改頁面輸入原密碼 驗證 PHP Web木馬掃描器代碼 v1.0 安全測試工具 用RMI和CORBA開發JAVA分布式程序 用mysql_fetch_array()獲取當前行數據的方法詳解
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved