STL函数对象 1 函数对象 1.1 函数对象概念 重载了函数调用操作符的类,其实例化的对象常称为函数对象 。且又因为函数对象使用重载的()时,行为类似函数调用,所以函数对象也叫仿函数
本质:函数对象(仿函数)是一个类 ,不是一个函数
1.2 函数对象使用 特点:
函数对象在使用时,可以像普通函数那样调用, 可以有参数,可以有返回值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class MyAdd {public : int operator () (int v1,int v2) { return v1 + v2; } };int main () { MyAdd myAdd; cout << myAdd (10 , 10 ) << endl; return 0 ; }
函数对象超出普通函数的概念,函数对象可以有自己的状态。(普通的函数想添加某些计数变量时,一般使用全局变量,而函数对象可以在类中定义自己的属性)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class MyPrint {public : MyPrint () { count = 0 ; } void operator () (string test) { cout << test << endl; count++; } int count; };int main () { MyPrint myPrint; myPrint ("hello world" ); myPrint ("hello world" ); myPrint ("hello world" ); cout << "myPrint调用次数为: " << myPrint.count << endl; return 0 ; }
hello world hello world hello world myPrint调用次数为: 3
经典用法就是作为仿函数作为某些算法的参数,例如按条件查找元素算法。
通常这些算法会希望传入一个谓词的参数(会定义为pred)
find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2 谓词 2.1 谓词概念
返回bool类型的仿函数称为谓词
如果operator()接受一个参数,那么叫做一元谓词
如果operator()接受两个参数,那么叫做二元谓词
2.2 一元谓词 operator()接受一个参数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include <iostream> #include <vector> #include <algorithm> using namespace std;class GreaterFive {public : bool operator () (int elm) { return elm >5 ; } };int main () { vector<int > v; v.push_back (1 ); v.push_back (6 ); v.push_back (2 ); vector<int >::iterator it = find_if (v.begin (), v.end (), GreaterFive ()); if (it == v.end ()) cout << "没找到!" << endl; else cout << "找到:" << *it << endl; return 0 ; }
找到:6
2.3 二元谓词 operator()接受两个参数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include <iostream> #include <vector> #include <algorithm> using namespace std;void printVector (vector<int > &v) { for (vector<int >::iterator it = v.begin (); it != v.end (); it++){ cout << *it << " " ; } cout << endl; }class MyCompare {public : bool operator () (int num1, int num2) { return num1 > num2; } };int main () { vector<int > v; v.push_back (10 ); v.push_back (40 ); v.push_back (20 ); v.push_back (30 ); v.push_back (50 ); sort (v.begin (), v.end ()); printVector (v); sort (v.begin (), v.end (), MyCompare ()); printVector (v); return 0 ; }
10 20 30 40 50 50 40 30 20 10
3 内建函数对象 3.1 内建函数对象的概念 概念:
分类:
用法:
这些仿函数所产生的对象,用法和一般函数完全相同
使用内建函数对象,需要引入头文件 #include<functional>
3.2 算术仿函数 功能描述:
实现四则运算
其中negate是一元运算,其他都是二元运算
仿函数原型:
template<class T> T plus<T>
//加法仿函数
template<class T> T minus<T>
//减法仿函数
template<class T> T multiplies<T>
//乘法仿函数
template<class T> T divides<T>
//除法仿函数
template<class T> T modulus<T>
//取模仿函数
template<class T> T negate<T>
//取反仿函数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <iostream> #include <functional> using namespace std;int main () { plus<int > p; int a = p (10 ,30 ); cout << a << endl; negate<float > n; float b = n (3.14 ); cout << b << endl; return 0 ; }
40 -3.14
3.3 关系仿函数 功能描述:
仿函数原型:
template<class T> bool equal_to<T>
//等于
template<class T> bool not_equal_to<T>
//不等于
template<class T> bool greater<T>
//大于,较常用
template<class T> bool greater_equal<T>
//大于等于
template<class T> bool less<T>
//小于
template<class T> bool less_equal<T>
//小于等于
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include <iostream> #include <vector> #include <functional> #include <algorithm> using namespace std;void printVector (vector<int >&v) { for (vector<int >::iterator it = v.begin (); it != v.end (); it++) { cout << *it << " " ; } cout << endl; }class MyCompare {public : bool operator () (int v1, int v2) { return v1>v2; } };int main () { equal_to<int > e; bool flag = e (1 ,2 ); cout << "flag = " << flag << endl; vector<int > v; v.push_back (10 ); v.push_back (30 ); v.push_back (50 ); v.push_back (40 ); v.push_back (20 ); printVector (v); sort (v.begin (),v.end (),greater <int >()); printVector (v); return 0 ; }
flag = 0 10 30 50 40 20 50 40 30 20 10
3.4 逻辑仿函数 功能描述:
函数原型:
template<class T> bool logical_and<T>
//逻辑与
template<class T> bool logical_or<T>
//逻辑或
template<class T> bool logical_not<T>
//逻辑非
逻辑仿函数实际应用较少,了解即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include <iostream> #include <vector> #include <functional> #include <algorithm> using namespace std;void printVector (vector<bool >&v) { for (vector<bool >::iterator it = v.begin ();it!= v.end ();it++){ cout << *it << " " ; } cout << endl; }int main () { vector<bool > v; v.push_back (true ); v.push_back (false ); v.push_back (true ); v.push_back (false ); printVector (v); vector<bool > v2; v2.resize (v.size ()); transform (v.begin (), v.end (), v2.begin (), logical_not <bool >()); printVector (v2); return 0 ; }
1 0 1 0 0 1 0 1
STL常用算法 概述 :
算法主要是由头文件<algorithm>
<functional>
<numeric>
组成。
<algorithm>
是所有STL头文件中最大的一个,范围涉及到比较、 交换、查找、遍历操作、复制、修改等等
<numeric>
体积很小,只包括几个在序列上面进行简单数学运算的模板函数
<functional>
定义了一些模板类,用以声明函数对象。
1 常用遍历算法
for_each
//遍历容器
transform
//搬运容器到另一个容器中
1.1 for_each 功能描述:
实现遍历容器
在实际开发中是最常用遍历算法,需要熟练掌握
函数原型:
for_each(iterator beg, iterator end, _func);
// beg 开始迭代器
// end 结束迭代器
// _func 函数或者函数对象
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include <iostream> #include <vector> #include <algorithm> using namespace std;void print01 (int val) { cout << val << " " ; }class print02 { public : void operator () (int val) { cout << val << " " ; } };int main () { vector<int > v; for (int i = 0 ; i < 10 ; i++) { v.push_back (i); } for_each(v.begin (),v.end (), print01); cout << endl; for_each(v.begin (),v.end (), print02 ()); return 0 ; }
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
功能描述:
函数原型:
transform(iterator beg1, iterator end1, iterator beg2, _func);
//beg1 源容器开始迭代器
//end1 源容器结束迭代器
//beg2 目标容器开始迭代器
//_func 函数或者函数对象
注意:
搬运的目标容器必须要提前开辟空间,否则无法正常搬运
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <vector> #include <algorithm> class TransForm {public : int operator () (int val) { return val; } };class MyPrint {public : void operator () (int val) { cout << val << " " ; } };int main () { vector<int >v; for (int i = 0 ; i < 10 ; i++){ v.push_back (i); } vector<int >vTarget; vTarget.resize (v.size ()); transform (v.begin (), v.end (), vTarget.begin (), TransForm ()); for_each(vTarget.begin (), vTarget.end (), MyPrint ()); return 0 ; }
2 常用查找算法 掌握常用的查找算法
find
//按值查找元素
find_if
//按条件查找元素
adjacent_find
//查找相邻重复元素
binary_search
//二分查找有序序列的指定元素
count
//按值统计元素个数
count_if
//按条件统计元素个数
一般按值查找/统计自定义类型需要重载==,例如 find/ adjacent_find/ count
一般按条件查找/统计自定义类型需要给出谓词,例如 find_if/ count_if
2.1 find 按值查找元素 功能描述:
查找指定元素,找到返回指定元素的迭代器,找不到返回结束迭代器end()
函数原型:
find(iterator beg, iterator end, value);
// 按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置
// beg 开始迭代器
// end 结束迭代器
// value 查找的元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 #include <algorithm> #include <vector> #include <string> void test01 () { vector<int > v; for (int i = 0 ; i < 10 ; i++) { v.push_back (i + 1 ); } vector<int >::iterator it = find (v.begin (), v.end (), 5 ); if (it == v.end ()) { cout << "没有找到!" << endl; } else { cout << "找到:" << *it << endl; } }class Person {public : Person (string name, int age) { this ->m_Name = name; this ->m_Age = age; } bool operator ==(const Person& p) { if (this ->m_Name == p.m_Name && this ->m_Age == p.m_Age) { return true ; } return false ; }public : string m_Name; int m_Age; };void test02 () { vector<Person> v; Person p1 ("aaa" , 10 ) ; Person p2 ("bbb" , 20 ) ; Person p3 ("ccc" , 30 ) ; Person p4 ("ddd" , 40 ) ; v.push_back (p1); v.push_back (p2); v.push_back (p3); v.push_back (p4); vector<Person>::iterator it = find (v.begin (), v.end (), p2); if (it == v.end ()) { cout << "没有找到!" << endl; } else { cout << "找到姓名:" << it->m_Name << " 年龄: " << it->m_Age << endl; }
2.2 find_if 按条件查找元素 功能描述:
按条件查找元素,更加灵活,提供的仿函数可以改变不同的策略
函数原型:
find_if(iterator beg, iterator end, _Pred);
// 按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置
// beg 开始迭代器
// end 结束迭代器
// _Pred 函数或者谓词(返回bool类型的仿函数)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 class Person {public : Person (string name, int age) { this ->m_Name = name; this ->m_Age = age; }public : string m_Name; int m_Age; };class Greater20 {public : bool operator () (Person &p) { return p.m_Age > 20 ; } };int main () { vector<Person> v; Person p1 ("aaa" , 10 ) ; Person p2 ("bbb" , 20 ) ; Person p3 ("ccc" , 30 ) ; Person p4 ("ddd" , 40 ) ; v.push_back (p1); v.push_back (p2); v.push_back (p3); v.push_back (p4); vector<Person>::iterator it = find_if (v.begin (), v.end (), Greater20 ()); if (it == v.end ()) { cout << "没有找到!" << endl; } else { cout << "找到姓名:" << it->m_Name << " 年龄: " << it->m_Age << endl; } return 0 ; }
2.3 adjacent_find 查找相邻重复元素 功能描述:
查找相邻重复元素
内部其实也有一个判断是否相等的过程,所以使用自定义类型时,需要重载==
函数原型:
adjacent_find(iterator beg, iterator end);
// 查找相邻重复元素,返回相邻元素的第一个位置的迭代器
// beg 开始迭代器
// end 结束迭代器
面试题中如果出现查找相邻重复元素,记得用STL中的adjacent_find算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int main () { vector<int > v; v.push_back (1 ); v.push_back (3 ); v.push_back (3 ); v.push_back (2 ); vector<int >::iterator it = adjacent_find (v.begin (), v.end ()); if (it == v.end ()){ cout << "找不到!" << endl; } else { cout << "找到相邻重复元素为:" << *it << endl; } return 0 ; }
2.4 binary_search 二分查找有序序列的指定元素 功能描述:
二分查找指定元素是否存在。二分查找法查找效率很高,值得注意的是查找的容器中元素必须是有序序列
函数原型:
bool binary_search(iterator beg, iterator end, value);
// 查找指定的元素,查到 返回true 否则false
// beg 开始迭代器
// end 结束迭代器
// value 查找的元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 int main () { vector<int >v; for (int i = 0 ; i < 10 ; i++) { v.push_back (i); } bool ret = binary_search (v.begin (), v.end (),2 ); if (ret) { cout << "找到了" << endl; } else { cout << "未找到" << endl; } return 0 ; }
2.5 count 按值统计元素个数 功能描述:
函数原型:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 #include <algorithm> #include <vector> void test01 () { vector<int > v; v.push_back (1 ); v.push_back (4 ); v.push_back (3 ); v.push_back (4 ); v.push_back (4 ); int num = count (v.begin (), v.end (), 4 ); cout << "4的个数为: " << num << endl; }class Person {public : Person (string name, int age) { this ->m_Name = name; this ->m_Age = age; } bool operator ==(const Person & p) { if (this ->m_Age == p.m_Age) { return true ; } else { return false ; } } string m_Name; int m_Age; };void test02 () { vector<Person> v; Person p1 ("刘备" , 35 ) ; Person p2 ("关羽" , 35 ) ; Person p3 ("张飞" , 35 ) ; Person p4 ("赵云" , 30 ) ; v.push_back (p1); v.push_back (p2); v.push_back (p3); v.push_back (p4); Person p ("诸葛亮" ,35 ) ; int num = count (v.begin (), v.end (), p); cout << "num = " << num << endl; }
自定义数据类型需要重载==
2.6 count_if 按条件统计元素个数 功能描述:
函数原型:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 #include <algorithm> #include <vector> class Greater4 {public : bool operator () (int val) { return val >= 4 ; } };void test01 () { vector<int > v; v.push_back (1 ); v.push_back (2 ); v.push_back (4 ); v.push_back (5 ); v.push_back (3 ); v.push_back (4 ); v.push_back (4 ); int num = count_if (v.begin (), v.end (), Greater4 ()); cout << "大于4的个数为: " << num << endl; }class Person {public : Person (string name, int age) { this ->m_Name = name; this ->m_Age = age; } string m_Name; int m_Age; };class AgeLess35 {public : bool operator () (const Person &p) { return p.m_Age < 35 ; } };void test02 () { vector<Person> v; Person p1 ("刘备" , 35 ) ; Person p2 ("关羽" , 35 ) ; Person p3 ("张飞" , 35 ) ; Person p4 ("赵云" , 30 ) ; Person p5 ("曹操" , 25 ) ; v.push_back (p1); v.push_back (p2); v.push_back (p3); v.push_back (p4); v.push_back (p5); int num = count_if (v.begin (), v.end (), AgeLess35 ()); cout << "小于35岁的个数:" << num << endl; }
总结: 按值统计用count,按条件统计用count_if
3 常用排序算法
sort
// 对容器内元素进行排序
random_shuffle
// 洗牌 指定范围内的元素随机调整次序
merge
// 容器元素合并,并存储到另一容器中
reverse
// 反转指定范围的元素
3.1 sort 功能描述:
函数原型:
sort(iterator beg, iterator end, _Pred);
// 按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置
// beg 开始迭代器
// end 结束迭代器
// _Pred 函数对象
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std;class myPrint {public : void operator () (int val) { cout << val << " " ; } };int main () { vector<int > v; v.push_back (10 ); v.push_back (30 ); v.push_back (50 ); v.push_back (20 ); v.push_back (40 ); sort (v.begin (), v.end ()); for_each(v.begin (), v.end (), myPrint); cout << endl; sort (v.begin (), v.end (), greater <int >()); for_each(v.begin (), v.end (), myPrint ()); cout << endl; return 0 ; }
3.2 random_shuffle 功能描述:
函数原型:
使用时记得加随机数种子
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <iostream> #include <vector> #include <algorithm> #include <ctime> using namespace std;class myPrint {public : void operator () (int val) { cout << val << " " ; } };int main () { srand ((unsigned int )time (NULL )); vector<int > v; for (int i = 0 ; i < 10 ;i++) { v.push_back (i); } for_each(v.begin (), v.end (), myPrint ()); cout << endl; random_shuffle (v.begin (), v.end ()); for_each(v.begin (), v.end (), myPrint ()); cout << endl; return 0 ; }
3.3 merge 功能描述:
将两个已经排好序 的序列合并为一个有序的序列。注意两个容器必须是有序的 ,可以是不同的容器
函数原型:
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
// beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class myPrint {public : void operator () (int val) { cout << val << " " ; } };int main () { vector<int > v1; vector<int > v2; for (int i = 0 ; i < 10 ; i++) { v1.push_back (i); v2.push_back (i + 5 ); } vector<int > vtarget; vtarget.resize (v1.size () + v2.size ()); merge (v1.begin (), v1.end (), v2.begin (), v2.end (), vtarget.begin ()); for_each(vtarget.begin (), vtarget.end (), myPrint ()); cout << endl; return 0 ; }
0 1 2 3 4 5 5 6 6 7 7 8 8 9 9 10 11 12 13 14
3.4 reverse 功能描述:
函数原型:
reverse反转区间内元素,面试题可能涉及到
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class myPrint {public : void operator () (int val) { cout << val << " " ; } };int main () { vector<int > v; v.push_back (10 ); v.push_back (30 ); v.push_back (50 ); v.push_back (20 ); v.push_back (40 ); cout << "反转前: " << endl; for_each(v.begin (), v.end (), myPrint ()); cout << endl; cout << "反转后: " << endl; reverse (v.begin (), v.end ()); for_each(v.begin (), v.end (), myPrint ()); cout << endl; return 0 ; }
反转前: 10 30 50 20 40 反转后: 40 20 50 30 10
4 常用拷贝和替换算法
copy
// 容器内指定范围的元素拷贝到另一容器中
replace
// 将容器内指定范围的旧元素修改为新元素
replace_if
// 容器内指定范围满足条件的元素替换为新元素
swap
// 互换两个容器的元素
4.1 copy 功能描述:
函数原型:
目标容器记得提前开辟空间
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int main () { vector<int > v1; for (int i = 0 ; i < 10 ; i++) { v1.push_back (i + 1 ); } vector<int > v2; v2.resize (v1.size ()); copy (v1.begin (), v1.end (), v2.begin ()); for_each(v2.begin (), v2.end (), myPrint ()); cout << endl; return 0 ; }
4.2 replace 功能描述:
函数原型:
显然自定义类型需要重载==
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 int main () { vector<int > v; v.push_back (20 ); v.push_back (30 ); v.push_back (20 ); v.push_back (40 ); v.push_back (50 ); v.push_back (10 ); v.push_back (20 ); cout << "替换前:" << endl; for_each(v.begin (), v.end (), myPrint ()); cout << endl; cout << "替换后:" << endl; replace (v.begin (), v.end (), 20 ,2000 ); for_each(v.begin (), v.end (), myPrint ()); cout << endl; return 0 ; }
4.3 replace_if 功能描述:
将区间内满足条件的元素,替换成指定元素。可以利用仿函数灵活筛选满足的条件
函数原型:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class ReplaceGreater30 {public : bool operator () (int val) { return val >= 30 ; } };int main () { vector<int > v; v.push_back (20 ); v.push_back (30 ); v.push_back (20 ); v.push_back (40 ); v.push_back (50 ); v.push_back (10 ); v.push_back (20 ); cout << "替换前:" << endl; for_each(v.begin (), v.end (), myPrint ()); cout << endl; cout << "替换后:" << endl; replace_if (v.begin (), v.end (), ReplaceGreater30 (), 3000 ); for_each(v.begin (), v.end (), myPrint ()); cout << endl; return 0 ; }
4.4 swap 功能描述:
函数原型:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 void test01 () { vector<int > v1; vector<int > v2; for (int i = 0 ; i < 10 ; i++) { v1.push_back (i); v2.push_back (i+100 ); } cout << "交换前: " << endl; for_each(v1.begin (), v1.end (), myPrint ()); cout << endl; for_each(v2.begin (), v2.end (), myPrint ()); cout << endl; cout << "交换后: " << endl; swap (v1, v2); for_each(v1.begin (), v1.end (), myPrint ()); cout << endl; for_each(v2.begin (), v2.end (), myPrint ()); cout << endl; }
5 常用算术生成算法 算术生成算法属于小型算法,使用时包含的头文件为 #include <numeric>
accumulate
// 计算容器元素累计总和
fill
// 向容器中添加元素
5.1 accumulate 功能描述:
函数原型:
accumulate(iterator beg, iterator end, value);
// 计算容器元素累计总和
// beg 开始迭代器
// end 结束迭代器
// value 起始值,最后的结果会加上这个起始值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include <numeric> #include <vector> int main () { vector<int > v; for (int i = 0 ; i <= 100 ; i++) { v.push_back (i); } int total = accumulate (v.begin (), v.end (), 0 ); cout << "total = " << total << endl; int total1 = accumulate (v.begin (), v.end (), 1000 ); cout << "total1 = " << total1 << endl; return 0 ; }
total = 5050 total1 = 6050
5.2 fill 功能描述:
函数原型:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <numeric> #include <vector> #include <algorithm> class myPrint {public : void operator () (int val) { cout << val << " " ; } };int main () { vector<int > v; v.resize (10 ); fill (v.begin (), v.end (), 100 ); for_each(v.begin (), v.end (), myPrint ()); cout << endl; return 0 ; }
6 常用集合算法
6.1 set_intersection 功能描述:
求两个容器(不要求是集合)的交集,两个容器必须是有序序列
函数原型:
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
// 返回值是交集中最后一个元素的迭代器地址
// beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器
目标容器开辟空间需要从两个容器中取小值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <vector> #include <algorithm> class myPrint {public : void operator () (int val) { cout << val << " " ; } };int main () { vector<int > v1; vector<int > v2; for (int i = 0 ; i < 10 ; i++) { v1.push_back (i); v2.push_back (i+5 ); } vector<int > vTarget; vTarget.resize (min (v1.size (), v2.size ())); vector<int >::iterator itEnd = set_intersection (v1.begin (), v1.end (), v2.begin (), v2.end (), vTarget.begin ()); for_each(vTarget.begin (), itEnd, myPrint ()); cout << endl; return 0 ; }
6.2 set_union 功能描述:
求两个容器(不要求是集合)的并集,两个容器必须是有序序列
函数原型:
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
// 返回值是并集中最后一个元素的迭代器地址
// beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器
目标容器开辟空间需要从两个容器中取大值
代码同上,改个函数名和开辟空间取最大值即可
6.3 set_difference 功能描述:
求两个容器(不要求是集合)的差集,两个容器必须是有序序列
函数原型:
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
// 返回值是差集中最后一个元素的迭代器地址
// beg1 容器1开始迭代器 // end1 容器1结束迭代器 // beg2 容器2开始迭代器 // end2 容器2结束迭代器 // dest 目标容器开始迭代器
目标容器开辟空间需要从两个容器中取大值 ,而且注意差集的顺序不同,结果也不同
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include <vector> #include <algorithm> class myPrint {public : void operator () (int val) { cout << val << " " ; } };int main () { vector<int > v1; vector<int > v2; for (int i = 0 ; i < 10 ; i++) { v1.push_back (i); v2.push_back (i+5 ); } vector<int > vTarget; vTarget.resize ( max (v1.size () , v2.size ())); cout << "v1与v2的差集为: " << endl; vector<int >::iterator itEnd = set_difference (v1.begin (), v1.end (), v2.begin (), v2.end (), vTarget.begin ()); for_each(vTarget.begin (), itEnd, myPrint ()); cout << endl; cout << "v2与v1的差集为: " << endl; itEnd = set_difference (v2.begin (), v2.end (), v1.begin (), v1.end (), vTarget.begin ()); for_each(vTarget.begin (), itEnd, myPrint ()); cout << endl; return 0 ; }