STL学习笔记非变易算法
STL学习笔记--非变易算法
非变易算法
C++ STL 的非变易算法（Non-mutating algorithm）是一组不破坏操作数据的模板函数，用来对序列数据进行逐个处理、元素查找、子序列搜索、统计和匹配。作为算法函数参数的迭代器，一般为 Input Iterator 输入迭代器，具有 "++" 迭代和 "*" 访问操作。通过迭代器的元素遍历，可对迭代器区间所界定的元素进行操作。因此，非变易算法具有极为广泛的适用性，基本上可应用于各种容器。
目录：
逐个容器元素 for_each
查找容器元素 find
条件查找容器元素 find_if
邻近查找容器元素 adjacent_find
范围查找容器元素 find_first_of
统计等于某值的容器元素个数 count
条件统计容器元素个数 count_if
元素不匹配查找 mismatch
元素相等判断 equal
子序列搜索 search
重复元素子序列搜索 search_n
最后一个子序列搜索 find_end
逐个容器元素 for_each
1 /* 下面的示例程序将 list 链表容器的元素，调用 for_each 算法函数，通过 print 函数对象，将各个链表的元素乘以3后打印，并输出元素个数
2 */
3 -------------------------------------------------------- 应用 for_each 算法遍历 list 容器
4 #include <algorithm> // 这个头文件很重要的哦
5 #include <list>
6 #include <iostream>
7 using namespace std;
8
9 struct print
10 {
11 int count; // 打印的元素计数
12 print(){count= 0 ;}
13 void operator () ( int x)
14 {
15 cout << 3 *x << endl;
16 count++ ;
17 }
18 };
19
20 int main()
21 {
22 // 双向链表初始化
23 list< int > lInt;
24 lInt.push_back( 29 );
25 lInt.push_back( 32 );
26 lInt.push_back( 16 );
27 lInt.push_back( 22 );
28 lInt.push_back( 28 );
29 lInt.push_back( 27 );
30
31 // 打印链表的元素
32 print p = for_each(lInt.begin(), lInt.end(), print());
33 // 打印的元素个数
34 cout << " 元素个数为： " <<p.count << endl;
35
36 return 0 ;
37 }
查找容器元素 find
1 /* 下面示例程序利用 find 算法函数查找 list 链表中第一个值为 14 的元素
2 */
3 -------------------------------------------------------- 应用 find 算法查找 list 容器的元素
4 #include <algorithm>
5 #include <list>
6 #include <iostream>
7 using namespace std;
8 int main()
9 {
10 // 双向链表初始化
11 list< int > lInt;
12 lInt.push_back( 100 );
13 lInt.push_back( 10 );
14 lInt.push_back( 14 );
15 lInt.push_back( 13 );
16 lInt.push_back( 14 );
17 lInt.push_back( 40 );
18
19 // 查找元素 14
20 list< int >::iterator iLocation = find(lInt.begin(), lInt.end(), 14 );
21 if (iLocation != lInt.end())
22 cout << " 找到元素14 " << endl;
23
24 // 打印第一个14元素前面的那个元素。即打印元素 10
25 cout << " 前一个元素为： " << *(--iLocation) << endl;
26
27 return 0 ;
28 }
条件查找容器元素 find_if
1 /* 下面示例程序使用 find_if 算法在 vector 向量容器上查找首个可被5整除的元素，程序输出为“找到第一个能被5整除的元素15，元素的索引位置为2”
2 */
3 -------------------------------------------------------- 应用 find_if 算法条件查找 vector 容器的元素
4 #include <algorithm>
5 #include <vector>
6 #include <iostream>
7 using namespace std;
8
9 // 谓词判断函数 divby5
10 bool divby5( int x)
11 {
12 return x% 5 ? 0 : 1 ;
13 }
14
15 int main()
16 {
17 vector< int > vInt( 20 ); // 可以参考之前对 vector 的介绍
18 for (unsigned int i= 0 ; i<vInt.size(); i++ )
19 vInt[i] = (i+ 1 )*(i+ 3 );
20
21 vector< int > ::iterator iLocation;
22 iLocation = find_if(vInt.begin(), vInt.end(), divby5);
23
24 if (iLocation != vInt.end())
25 cout << " 找到第一个能被5整除的元素: "
26 << *iLocation << endl // 打印15
27 << " 元素的索引位置为: "
28 << iLocation-vInt.begin() << endl; // 打印2
29
30 return 0 ;
31 }
邻近查找容器元素 adjacent_find
1 /* 调用 adjacent_find 算法函数找出邻近相等的元素11(链表中，有2个11是临近的)，再利用是否为奇偶相同，做谓词判断，找出首先同为奇数的 9和11.
2 */
3 -------------------------------------------------------- 应用 adjacent_find 算法临近查找容器的元素
4 #include <algorithm>
5 #include <list>
6 #include <iostream>
7 using namespace std;
8
9 bool parity_equal ( int x, int y)
10 {
11 return (x-y)% 2 == 0 ? 1 : 0 ;
12 }
13
14 int main()
15 {
16 // 初始化链表
17 list< int > lInt;
18 lInt.push_back( 3 );
19 lInt.push_back( 6 );
20 lInt.push_back( 9 );
21 lInt.push_back( 11 );
22 lInt.push_back( 11 );
23 lInt.push_back( 18 );
24 lInt.push_back( 20 );
25 lInt.push_back( 20 );
26 // 查找邻接相等的元素
27 list< int >::iterator iResult = adjacent_find(lInt.begin(), lInt.end());
28 if (iResult != lInt.end())
29 {
30 cout << " 发现链表有两个邻接的元素相等 " << endl;
31 cout << *iResult << endl; // 打印第1 个11
32 ++ iResult;
33 cout << *iResult << endl; // 打印第2 个11
34 }
35
36 // 查找奇偶性相同的邻接元素
37 iResult = adjacent_find(lInt.begin(), lInt.end(), parity_equal);
38 if (iResult != lInt.end())
39 {
40 cout << " 发现有两个邻接元素的奇偶性相同 " << endl;
41 cout << *iResult << endl; // 打印 9
42 ++ iResult;
43 cout << *iResult << endl; // 打印 11
44 }
45
46 return 0 ;
47 }
范围查找容器元素 find_first_of
1 /* 下面示例程序在字符串 "abcdef7ghijklmn" 中查找首个出现在字符串 "zyx3pr7ys" 的字符，结果当然是字符 7
2 */
3 -------------------------------------------------------- 应用 find_first_of 算法范围查找容器元素
4 #include <algorithm>
5 #include <iostream>
6 using namespace std;
7 int main()
8 {
9 // 定义2个字符串
10 char * str1 = " abcdef7ghijklmn " ;
11 char * str2 = " zyx3pr7ys " ;
12 // 范围查找 str1 于 str2 中
13 char * result = find_first_of(str1, str1 + strlen(str1),
14 str2, str2 + strlen(str2));
15 cout << " 字符串 str1 的第一个出现在 str2 的字符为： "
16 << *result << endl; // 打印 7
17
18 return 0 ;
19 }
统计等于某值的容器元素个数 count
1 /* 下面的示例程序链入100个20的余数到双向链表 list 中，然后统计其中等于 9 的元素个数。
2 */
3
4 -------------------------------------------------------- 应用 count 算法统计等于某值的容器元素个数
5 #include <algorithm>
6 #include <list>
7 #include <iostream>
8 using namespace std;
9 int main()
10 {
11 // 链表初始化
12 list< int > lInt;
13 for ( int i= 0 ; i< 100 ; i++ )
14 lInt.push_back(i% 20 );
15 // 统计链表中等于 value 值的元素个数
16 int num = 0 ;
17 int value = 9 ;
18 num = count(lInt.begin(), lInt.end(), value);
19 cout << " 链表中元素等于 value 的元素个数为： "
20 << num << endl; // 打印5
21
22 return 0 ;
23 }
条件统计容器元素个数 count_if
1 /* 下面示例程序，将学生记录放入使用红黑树的 map 容器，然后利用一元谓词判断 setRange20_30 ，统计年龄在20至30岁之间的学生人数
2 */
3
4 -------------------------------------------------------- 应用 count_if 算法统计满足条件的记录数
5 #pragma warning(disable:4786)
6 #include <algorithm>
7 #include <map>
8 #include <iostream>
9 using namespace std;
10
11 // 学生记录结构体
12 struct StudentRecord
13 {
14 struct StudentInfo
15 {
16 char * name;
17 int year;
18 char * addr;
19 };
20 int id; // 学号
21 StudentInfo sf; // 学生信息
22 StudentRecord( int id_, char * name_, int year_, char * addr_)
23 {
24 id = id_;
25 sf.name = name_;
26 sf.year = year_;
27 sf.addr = addr_;
28 }
29 };
30
31 bool setRange20_30(pair< int , StudentRecord::StudentInfo> s)
32 {
33 // 20 < x < 30
34 if (s.second.year > 20 && s.second.year < 30 )
35 return 1 ;
36
37 return 0 ;
38 }
39
40 int main()
41 {
42 // 学生数据
43 StudentRecord st1 = StudentRecord( 1 , " 李强 " , 21 , " 北京 " );
44 StudentRecord st2 = StudentRecord( 2 , " 李文 " , 29 , " 山东 " );
45 StudentRecord st3 = StudentRecord( 3 , " 张三 " , 12 , " 江苏 " );
46 StudentRecord st4 = StudentRecord( 4 , " 李四 " , 23 , " 武汉 " );
47 StudentRecord st5 = StudentRecord( 5 , " 王五 " , 32 , " 上海 " );
48
49 // 映照容器
50 map< int , StudentRecord::StudentInfo> m;
51 // 插入 5条学生记录
52 pair< int , StudentRecord::StudentInfo> pairSt1(st1.id, st1.sf);
53 m.insert(pairSt1);
54 pair< int , StudentRecord::StudentInfo> pairSt2(st2.id, st2.sf);
55 m.insert(pairSt2);
56 pair< int , StudentRecord::StudentInfo> pairSt3(st3.id, st3.sf);
57 m.insert(pairSt3);
58 pair< int , StudentRecord::StudentInfo> pairSt4(st4.id, st4.sf);
59 m.insert(pairSt4);
60 pair< int , StudentRecord::StudentInfo> pairSt5(st5.id, st5.sf);
61 m.insert(pairSt5);
62
63 // 条件统计
64 int num = 0 ;
65 num = count_if(m.begin(), m.end(), setRange20_30);
66 cout << " 年龄介于20至30之间的学生人数为： "
67 << num << endl; // 打印 3
68
69 return 0 ;
70 }
元素不匹配查找 mismatch
1 /* 下面示例程序，分别使用了 mismatch 算法函数的两种形式。
2 */
3
4 -------------------------------------------------------- 应用 msimatch 算法比较两个序列的元素
5 #include <algorithm>
6 #include <vector>
7 #include <iostream>
8 using namespace std;
9
10 bool strEqual( const char * s1, const char * s2)
11 {
12 return strcmp(s1, s2) == 0 ? 1 : 0 ;
13 }
14
15 int main()
16 {
17 vector< int > v1, v2;
18 v1.push_back( 2 );
19 v1.push_back( 0 );
20 v1.push_back( 0 );
21 v1.push_back( 6 );
22
23 v2.push_back( 2 );
24 v2.push_back( 0 );
25 v2.push_back( 0 );
26 v2.push_back( 7 );
27
28 // v1 和 v2 不匹配检查
29 pair<vector< int >::iterator, vector< int >::iterator> result = mismatch(v1.begin(), v1.end(), v2.begin());
30
31 if (result.first == v1.end() && result.second == v1.end())
32 cout << " v1 和 v2 完全相同 " << endl;
33 else
34 cout << " v1 和 v2 不相同，不匹配的数是：\n "
35 << *result.first << endl
36 << *result.second << endl << endl;
37
38
39 // 初始化字符串 s1、s2
40 char * s1[]={ " apple " , " pear " , " watermelon " , " banana " , " grape " };
41 char * s2[]={ " apple " , " pears " , " watermelons " , " banana " , " grape " };
42 // s1 和 s2 不匹配检查
43 pair< char **, char **> result2 = mismatch(s1, s1+ 5 , s2, strEqual);
44 if (result2.first == s1+ 5 && result2.second == s2+ 5 )
45 cout << " s1和s2完全相同 " << endl;
46 else
47 cout << " s1 与 s2不相同，不匹配的字符串为：\n "
48 << s1[result2.first - s1] << endl
49 << s2[result2.second - s2] << endl << endl;
50
51 return 0 ;
52 }
元素相等判断 equal
1 /* 下面示例程序，利用二元谓词判断 absEqual ，判断出两个 vector 向量容器的元素均绝对值相等。
2 */
3
4 -------------------------------------------------------- 应用 equal 算法判断容器元素是否绝对值相等
5 #include <algorithm>
6 #include <vector>
7 #include <iostream>
8 using namespace std;
9
10 bool absEqual( int a, int b)
11 {
12 return (a==abs(b) || abs(a)==b) ? 1 : 0 ;
13 }
14
15 int main()
16 {
17 vector< int > v1( 5 );
18 vector< int > v2( 5 );
19 for (unsigned int i= 0 ; i<v1.size(); i++ )
20 {
21 v1[i] = i;
22 v2[i] = - 1 * i;
23 }
24
25 // v1、v2 相等检查
26 if (equal(v1.begin(), v1.end(), v2.begin(), absEqual))
27 cout << " v1 和 v2 元素的绝对值完全相等 " << endl;
28 else
29 cout << " v1 和 v2 元素的绝对值不完全相等 " << endl;
30
31 return 0 ;
32 }
子序列搜索 search
1 /* 下面示例程序，搜索 vector 向量 V1={5, 6, 7, 8, 9}是否包含子序列向量容器 v2={7, 8}.
2 */
3
4 -------------------------------------------------------- 应用 search 方法搜索子序列
5 #include <algorithm>
6 #include <vector>
7 #include <iostream>
8 using namespace std;
9 int main()
10 {
11 // 初始化向量 v1
12 vector< int > v1;
13 v1.push_back( 5 );
14 v1.push_back( 6 );
15 v1.push_back( 7 );
16 v1.push_back( 8 );
17 v1.push_back( 9 );
18 // 初始化向量 v2
19 vector< int > v2;
20 v2.push_back( 7 );
21 v2.push_back( 8 );
22 // 检查 v2 是否构成 v1 的子序列
23 vector< int > ::iterator iterLocation;
24 iterLocation = search(v1.begin(), v1.end(), v2.begin(), v2.end());
25 // 打印从 v1[2]开始匹配
26 if (iterLocation != v1.end())
27 cout << " v2 的元素包含在 v1 中，起始元素为： "
28 << " v1[ " << iterLocation - v1.begin() << " ] \n " ;
29 else
30 cout << " v2的元素不包含在v1中. " << endl;
31
32 return 0 ;
33 }
重复元素子序列搜索 search_n
1 /* 下面示例程序，搜索出向量 v={1, 8, 8, 8, 6, 6, 8}中有3个连续元素8、没有4个连续的元素8，以及有2个连续元素6
2 */
3
4 -------------------------------------------------------- 应用 search_n 算法搜索重复元素值
5 #include <algorithm>
6 #include <vector>
7 #include <iostream>
8 using namespace std;
9 int main()
10 {
11 // 初始化向量 v
12 vector< int > v;
13 v.push_back( 1 );
14 v.push_back( 8 );
15 v.push_back( 8 );
16 v.push_back( 8 );
17 v.push_back( 6 );
18 v.push_back( 6 );
19 v.push_back( 8 );
20
21 // 查找子序列 {8, 8, 8}
22 vector< int > ::iterator iLocation;
23 iLocation = search_n(v.begin(), v.end(), 3 , 8 );
24 if (iLocation != v.end())
25 cout << " 在v中找到3个连续的元素8 " << endl;
26 else
27 cout << " v中没有3个连续的元素8 " << endl;
28
29 // 查找子序列 {8, 8, 8, 8}
30 iLocation = search_n(v.begin(), v.end(), 4 , 8 );
31 if (iLocation != v.end())
32 cout << " 在v中找到4个连续的元素8 " << endl;
33 else
34 cout << " v中没有4个连续的元素8 " << endl;
35
36 // 查找子序列{6, 6}
37 iLocation = search_n(v.begin(), v.end(), 2 , 6 );
38 if (iLocation != v.end())
39 cout << " 在v中找到2个连续的元素6 " << endl;
40 else
41 cout << " v中没有2个连续的元素6 " << endl;
42
43 return 0 ;
44 }
最后一个子序列搜索 find_end
1 /* 下面示例程序，搜索向量 v1={-5, 1, 2, -6, -8, 1, 2, -11}中最后一个与V2={1, 2}匹配的子序列，打印输出为 "v1中找到最后一个匹配v2的子序列，位置在 v1[5]"
2 */
3 -------------------------------------------------------- 应用 find_end 算法搜索最后一个匹配子序列
4 #include <algorithm>
5 #include <vector>
6 #include <iostream>
7 using namespace std;
8 int main()
9 {
10 // 初始化向量 v1
11 vector< int > v1;
12 v1.push_back(- 5 );
13 v1.push_back( 1 );
14 v1.push_back( 2 );
15 v1.push_back(- 6 );
16 v1.push_back(- 8 );
17 v1.push_back( 1 );
18 v1.push_back( 2 );
19 v1.push_back(- 11 );
20
21 // 初始化向量 v2
22 vector< int > v2;
23 v2.push_back( 1 );
24 v2.push_back( 2 );
25
26 // v1中查找最后一个子序列 v2
27 vector< int > ::iterator iLocation;
28 iLocation = find_end(v1.begin(), v1.end(), v2.begin(), v2.end());
29
30 // 打印子序列在 v1 的起始位置 v[5]
31 if (iLocation != v1.end())
32 cout << " v1中找到最后一个匹配 v2 的子序列，位置在 "
33 << " v1[ " << iLocation - v1.begin() << " ] \n " ;
34
35
36 return 0 ;
37 }
------------ 非变易算法小结
C++ STL 算法库中的非变易算法，是一些原则上不会变更操作数据的算法，包括可逐元素循环提交处理的 for_each 算法、用于元素查找的 find/find_if/adjacent_find/find_first_of 算法、用于统计元素个数的 count/count_if 算法、两序列匹配比较 mismatch/equal 算法和子序列搜索 search/search_n/find_end 算法。
作者： Music__Liang
出处： http://www.cnblogs.com/music-liang/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利.
分类: STL学习笔记
标签: STL , C++ , 算法
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did46192