2019 June 23 CPP基础

第十四章 STL算法第一节

算法简介

  1. 算法概述
    1. 算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。
    2. <algorithm>是所有STL头文件中最大的一个，其中常用到的功能范围涉及到:比较、交换、查找、遍历操作、复制、修改、反转、排序、合并等等
    3. <numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。
    4. <functional>中则定义了一些模板类，用以声明函数对象。
    5. STL提供了大量实现算法的模版函数，只要我们熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能，从而大大地提升效率。
  2. STL中算法分类
    1. 按操作对象分类
      1. 直接改变容器的内容
      2. 将原容器的内容复制一份,修改其副本,然后传回该副本
    2. 功能:
      1. 非可变序列算法: 指不直接修改其所操作的容器内容的算法
        1. 计数算法: count、count_if
        2. 搜索算法: search、find、find_if、find_first_of、…
        3. 比较算法: equal、mismatch、lexicographical_compare
      2. 可变序列算法: 指可以修改它们所操作的容器内容的算法
        1. 删除算法: remove、remove_if、remove_copy、…
        2. 修改算法: for_each、transform
        3. 排序算法: sort、stable_sort、partial_sort、
      3. 排序算法: 包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作
      4. 数值算法: 对容器内容进行数值计算

算法中的函数对象

算法中函数对象和谓词

  1. 函数对象和谓词定义
    1. 函数对象:(就是前面讲的仿函数)
      1. 重载函数调用操作符的类（一个类重载了它的函数调用操作符，即”()”操作符），其对象常称为函数对象（function object），即它们是行为类似函数的对象
      2. 一个类对象，表现出一个函数的特征，就是通过对象名+(参数列表)的方式使用一个类对象，如果没有上下文，完全可以把它看作一个函数对待。
      3. 这是通过重载类的operator()来实现的。
      4. 在标准库中，函数对象被广泛地使用以获得弹性，标准库中的很多算法都可以使用函数对象或者函数来作为自定的回调行为;
    2. 谓词：
      1. 一元函数对象：函数参数1个；
      2. 二元函数对象：函数参数2个；
      3. 一元谓词: 函数参数1个，函数返回值是bool类型，可以作为一个判断式
        1. 谓词可以使一个仿函数，也可以是一个回调函数。
      4. 二元谓词: 函数参数2个，函数返回值是bool类型
    3. 容器算法迭代器的设计理念： 分清楚stl算法返回的值是迭代器还是谓词(函数对象)是stl算法入门的重要点
  2. 函数对象
    1. 实现： 
       #include<iostream>
 #include<vector>
 #include<algorithm>
 using namespace std;
        
 //函数模板
 template<typename T>
     void FuncShowElemt(const T &t) {
     cout << t << endl;
 }
        
 //函数对象：某个类重载了 ()
 //类模板
 template<typename T>
 class ShowElemt {
 private:
     	int n; //用于记录当前成员函数调用的次数
 public:
     	//构造函数
     	ShowElemt() {
     		n = 0;
     	}
     	//重载函数调用操作符
     	//加一个const，既可以传常量，也可以传变量，否则只能传常量
     	void operator()(const T &t) {
     		n++;
     		cout << t << endl;
     	}
            
     	//成员函数
     	void printCount() {
     		cout << "函数的调用次数：" << n << endl;
     	}
 };

    2. 函数对象与函数

       void test1() {
 	/****对象函数***/
 	//创建一个对象
 	ShowElemt<int> showElemt;
 	//调用对象的成员函数,看起来很像一个函数的调用，因此也叫做仿函数
 	showElemt(5);
 	//等价
 	//showElemt.operator()(5);
        
 	/****函数调用***/
 	FuncShowElemt<int>(8);
 	FuncShowElemt(8);
 }

    3. 函数对象的优点：可以保持一些状态

       void test2() {
     	//数组
     	vector<int> v1;
     	v1.push_back(1);
     	v1.push_back(2);
     	v1.push_back(3);
            
     	//for_each:用于遍历容器中的所有元素
     	//1. 传参为匿名函数对象
     	//ShowElemt<int>()： 匿名函数对象
     	for_each(v1.begin(), v1.end(), ShowElemt<int>());
            	
     	//2. 也可以传函数的地址，回调函数
     	for_each(v1.begin(), v1.end(), FuncShowElemt<int>);
            
     	//3. 查看函数的调用次数
     	ShowElemt<int> elemt;
     	//for_each算法：当函数对象做函数参数时，必须接收一下
     	elemt = for_each(v1.begin(), v1.end(), elemt);
     	elemt.printCount();
 }
      1. for_each算法：当函数对象做函数参数时，函数对象必须接收一下，为什么呢？
        1. 如果不接收，会发现elemt.printCount();打印为0,为何呢？

      2. 查看for_each的源码

         template<class _InIt,class _Fn> 
 inline _Fn for_each(_InIt _First, _InIt _Last, _Fn _Func)
 {	
     _Adl_verify_range(_First, _Last);
     auto _UFirst = _Get_unwrapped(_First);
     const auto _ULast = _Get_unwrapped(_Last);
     for (; _UFirst != _ULast; ++_UFirst)
     {
     _Func(*_UFirst);
     }
     return (_Func);
 }
        1. 参数都是值传递，非引用（指针）传递，因此，内部修改调用与外部无关
        2. 因此，当函数对象当做参数传入时，函数内部本质是调用浅拷贝，拷贝一个新的函数对象接收
        3. 所以外面的函数对象elemt任然不变
        4. 但是该函数的返回值却返回了内部拷贝的那个信函上对象值
        5. 因此，只要在外部接收一下该函数的返回值，既可以拿到函数内部的拷贝值
        6. 这就是为何外部的函数对象要接收该函数的返回值，然后打印才会有值的原因。
  3. 一元谓词案例:

    1. 举例：

       //一元谓词
 template<typename T>
 class lsdiv {
 private:
     	T divisor;
 public:
     	lsdiv(const T &divtor) {
     		this->divisor = divtor;
     	}
     	//一元谓词
     	bool operator()(T &t){
     		return (t%divisor == 0);
     	}
        
 };
        
 void test3() {
     	vector<int> v2;
     	for (int i = 10; i < 33; i++)
     	{
     		v2.push_back(i);
     	}
     	int a = 4;
     	lsdiv<int> mydiv(a);
     	vector<int>::iterator it;
     	//遍历容器中的所有元素，找到第一个能够被4整除的元素
     	//find_if:条件遍历,第三个参数是函数指针或者函数对象，返回值是迭代器
     	it = find_if(v2.begin(), v2.end(), mydiv);
     	if (it == v2.end()){ //说明没找到
     		cout << "容器中没有4的倍数的元素" << endl;
     	}else {//说明找到了
     		cout << "容器中第一个4的倍数的元素："<<*it << endl;
     	}
 }
      1. find_if算法：
        1. 条件遍历,第三个参数就是遍历条件，可以是函数指针或者函数对象
        2. 返回值是迭代器

        3. 源码：

           template<class _InIt,class _Pr>
 	_NODISCARD inline _InIt find_if(_InIt _First, const _InIt _Last, _Pr _Pred)
 	{	
                
 	_Adl_verify_range(_First, _Last);
 	auto _UFirst = _Get_unwrapped(_First);
 	const auto _ULast = _Get_unwrapped(_Last);
 	for (; _UFirst != _ULast; ++_UFirst)
 		{
 		//调用一元谓词
 		if (_Pred(*_UFirst))
 			{
 			break;
 			}
 		}

 	_Seek_wrapped(_First, _UFirst);
 	//返回迭代器
 	return (_First);
 }

  4. 二元函数对象

    1. 代码举例

       //二元函数对象
 template<typename T>
 class SumAdd {
 public:
 	T operator()(T t1, T t2) {
 		return t1 + t2;
 	}
 private:
        
 };
        
 void test4() {
 	vector<int> v1, v2;
 	vector<int> v3;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 	v2.push_back(2);
 	v2.push_back(4);
 	v2.push_back(6);
        
 	//将V3的大小设置为10
 	v3.resize(10);
 	//transform：遍历第一个容器中的元素与第二个容器中的相应位置元素按照最后一个函数处理，然后放入到v3容器中
 	transform(v1.begin(), v1.end(), v2.begin(), v3.begin(),SumAdd<int>());
        
 	//打印V3
 	for (vector<int>::iterator it = v3.begin(); it != v3.end(); it++) {
 		cout << *it << endl;
 	}
 }
        
 //使用
 int main() {
 	test4();
 	cout << "hello world ！" << endl;
 	getchar();
 	return 0;
 }

    2. stl算法：transform源码

       template<class _InIt1, class _InIt2, class _OutIt, class _Fn>
 inline
 	_OutIt transform(const _InIt1 _First1, const _InIt1 _Last1,
 		const _InIt2 _First2, _OutIt _Dest, _Fn _Func)
 	{	
        
 	//第一个容器
 	auto _UFirst1 = _Get_unwrapped(_First1);
 	const auto _ULast1 = _Get_unwrapped(_Last1);
 	const auto _Count = _Idl_distance<_InIt1>(_UFirst1, _ULast1);
 	//第二个容器
 	auto _UFirst2 = _Get_unwrapped_n(_First2, _Count);
 	auto _UDest = _Get_unwrapped_n(_Dest, _Count);
 	for (; _UFirst1 != _ULast1; ++_UFirst1, (void)++_UFirst2, ++_UDest)
 		{
 		*_UDest = _Func(*_UFirst1, *_UFirst2);
 		}
        
 	_Seek_wrapped(_Dest, _UDest);
 	return (_Dest);
 	}

  5. 二元谓词

     //二元谓词
 bool mycompare(const int &a, const int &b) {
 	return a < b;//从小到大排序
 }
 void test5() {
 	vector<int>v1(10);
 	for (int i = 0; i < 10; i++)
 	{
 		int temp = rand() % 100;
 		v1[i] = temp;
 	}
    	
 	//排序
 	sort(v1.begin(), v1.end(), mycompare);
 	//打印V1
 	for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) {
 		cout << *it << endl;
 	}
 }
  6. 二元谓词在set集合中的应用

    1. set容器的find函数，查找字符串时，区分大小写，但是可以设计成不区分大小写

       //先将set容器中的元素全部转化成小写，然后在按照一定顺序排序
 struct CompareNoCase
 {	
     	//注意一定要有const，否则报错：ERROR C3848:具有类型"const XXX" 的表达式会丢失一些 const-volatile 限定符
     	bool operator()(const string &str1, const string &str2) const{
     		string str_;
     		str_.resize(str1.size());
     		//字符串全部转为小写
     		transform(str1.begin(), str1.end(), str_.begin(), tolower);//tolower这个函数对象系统已经写好了---预定义函数对象 
     		string str2_;
     		str2_.resize(str2.size());
     		//字符串全部转为小写
     		transform(str2.begin(), str2.end(), str2_.begin(), tolower);//tolower这个函数对象系统已经写好了
     		return (str_ < str2_);
     	}
 };
        
        
 void test6() {
        	
     	set<string> st1;
     	st1.insert("bbb");
     	st1.insert("aaa");
     	st1.insert("ccc");
     	//如果换成"aAa",那么find就查找不到了，因为set容器的find成员函数区分大小写
     	set<string>::iterator it = st1.find("aAa");
     	if (it != st1.end())
     	{
     		cout << "查找到aaa" << endl;
     	}
     	else
     	{
     		cout << "没有查找到" << endl;
     	}
              
       //这么一弄，此时st2中的容器全部转成小写，而且从小到大排序
     	set<string, CompareNoCase> st2;
     	st2.insert("bbb");
     	st2.insert("aaa");
     	st2.insert("ccc");
              
       //只改变了容器的顺序，但是find就不会区分大小写了呢？---以后研究
     	set<string, CompareNoCase>::iterator it2 = st2.find("aAa");
     	if (it2 != st2.end())
     	{
     		cout << "（不分大小写）查找到aaa" << endl;
     	}
     	else
     	{
     		cout << "（不分大小写）没有查找到" << endl;
     	}
 }

预定义函数对象和函数适配器

预定义函数对象

  1. 预定义函数对象基本概念：标准模板库STL提前定义了很多预定义函数对象
    1. #include <functional> 必须包含。
  2. 算术函数对象
    1. 预定义的函数对象支持加、减、乘、除、求余和取反。调用的操作符是与type相关联的实例

    2. 举例：

       加法：plus<Types>
     plus<string> stringAdd;
     sres = stringAdd(sva1,sva2);
 减法：minus<Types>
 乘法：multiplies<Types>
 除法divides<Tpye>
 求余：modulus<Tpye>
 取反：negate<Type>
     negate<int> intNegate;
     ires = intNegate(ires);
     Ires= UnaryFunc(negate<int>(),Ival1);
  3. 关系函数对象

    1. 举例：

       等于equal_to<Tpye>
     equal_to<string> stringEqual;
     sres = stringEqual(sval1,sval2);
 不等于not_equal_to<Type>
 大于 greater<Type>
 大于等于greater_equal<Type>
 小于 less<Type>
 小于等于less_equal<Type>
  4. 逻辑函数对象

    1. 举例

       逻辑与 logical_and<Type>
     logical_and<int> indAnd;
     ires = intAnd(ival1,ival2);
     dres=BinaryFunc( logical_and<double>(),dval1,dval2);
 逻辑或logical_or<Type>
 逻辑非logical_not<Type>
     logical_not<int> IntNot;
     Ires = IntNot(ival1);
     Dres=UnaryFunc( logical_not<double>,dval1);

  5. 使用举例：

     void test7(){
 	plus<int> intAdd;
 	int x = 10;
 	int y = 20;
 	int z = intAdd(x, y); //等价于 x + y 
 	cout << z << endl;
    
 	plus<string> stringAdd;
 	string myc = stringAdd("aaa", "bbb");
 	cout << myc << endl;
    
 	vector<string> v1;
 	v1.push_back("bbb");
 	v1.push_back("aaa");
 	v1.push_back("ccc");
 	v1.push_back("zzzz");
    
 	//通常情况下，sort()用底层元素类型的小于操作符以升序排列容器的元素。
 	//为了降序，可以传递预定义的类模板greater,它调用底层元素类型的大于操作符：
 	cout << "sort()函数排序" << endl;;
 	//greater<string>()匿名函数对象
 	sort(v1.begin(), v1.end(), greater<string>()); //从大到小
 	for (vector<string>::iterator it = v1.begin(); it != v1.end(); it++)
 	{
 		cout << *it << endl;
 	}
    
 	vector<string> v2;
 	v2.push_back("bbb");
 	v2.push_back("aaa");
 	v2.push_back("ccc");
 	v2.push_back("zzzz");
 	v2.push_back("ccc");
 	string s1 = "ccc";
 	//求s1出现的次数
 	//本来貌似应该这么写，但是这么写错误，仅仅有3个参数，而且第三个参数是一个指针，或者函数对象
 	//int num = count_if(v1.begin(),v1.end(), equal_to<string>(),s1);
 	//bind2nd函数适配器：将预定义函数对象与参数绑定
 	//equal_to<string>()：有2个参数，左参数来自容器，右参数被绑定为s1，让容器中的每个元素与右参数s1进行比较
 	int num = count_if(v2.begin(), v2.end(), bind2nd(equal_to<string>(), s1));
 	cout << num << endl;
 }
    1. 分析：
      1. count_if 函数只有3个参数

      2. 源码如下：

         template<class _InIt,class _Pr>
 _NODISCARD inline _Iter_diff_t<_InIt> count_if(_InIt _First, _InIt _Last, _Pr _Pred)
 {	// count elements satisfying _Pred   //计算元素
     _Adl_verify_range(_First, _Last);
     auto _UFirst = _Get_unwrapped(_First);
     const auto _ULast = _Get_unwrapped(_Last);
     _Iter_diff_t<_InIt> _Count = 0;
     for (; _UFirst != _ULast; ++_UFirst)
     {
         if (_Pred(*_UFirst))   //函数返回yes,_count+1
         	{
         	   ++_Count;
         	}
     }
                    
     return (_Count);
 }
      3. 从上面可以看出，第三个参数是一个函数指针，或者函数对象
      4. 而且内部遍历调用时只传容器中的元素
      5. 那么问题来了，我们目的是想让元素中的值与一个字符串比较，那么这个函数应该有两个参数
      6. 即函数对象equal_to<string>()是2个对象,那么怎么办呢？
      7. 此时就用到了函数适配器—bind2nd
        1. 作用就是可以将一个二元函数的第二个参数设置成一个默认的值，然后在返回这个函数(对象)
        2. bind2nd(equal_to<string>(), s1),这么写就相当于equal_to(x,s1);,其中x是变量，s1是常量

函数适配器

  1. 理论知识：
    1. STL中已经定义了大量的函数对象，但是有时候需要对函数返回值进行进一步的简单计算，或者填上多余的参数，不能直接带入算法。
    2. 函数适配器实现了这一功能：将一种函数对象转化为另一种符合要求的函数对象。
    3. 函数适配器可以分为4大类：
      1. 绑定适配器(bind adaptor)
      2. 组合适配器(composite adaptor)
      3. 指针函数适配器(pointer function adaptor)
      4. 成员函数适配器(member function adaptor)

    4. 下图是STL中所有函数适配器

      pic-w50

    5. 直接构造STL中的函数适配器通常会导致冗长的类型声明。为简化函数适配器的构造，STL还提供了函数适配器辅助函数，借助于泛型自动推断技术，无需显式的类型声明便可实现函数适配器的构造。

      pic-w50

  2. 常用函数函数适配器
    1. 标准库提供一组函数适配器，用来特殊化或者扩展一元和二元函数对象。常用适配器是：
      1. 绑定器（binder）: binder通过把二元函数对象的一个实参绑定到一个特殊的值上，将其转换成一元函数对象。C＋＋标准库提供两种预定义的binder适配器：bind1st和bind2nd，前者把值绑定到二元函数对象的第一个实参上，后者绑定在第二个实参上。
      2. 取反器(negator) : negator是一个将函数对象的值翻转的函数适配器。标准库提供两个预定义的ngeator适配器：not1翻转一元预定义函数对象的真值,而not2翻转二元谓词函数的真值。

      3. 常用函数适配器列表如下：

         bind1st(op, value)
 bind2nd(op, value)
 not1(op)
 not2(op)
 mem_fun_ref(op)
 mem_fun(op)
 ptr_fun(op)
    2. 总结函数适配器bind2nd的作用：
      1. 将一个二元函数转化为一元函数
      2. 其中一个参数设置为默认参数value，另一个参数为变量

  3. 举例使用：

     //是否大于
 class IsGreat
 {
 public:
 	IsGreat(int i)
 	{
 		m_num = i;
 	}
 	//一元谓词
 	bool operator()(int &num)
 	{
 		if (num > m_num)
 		{
 			return true;
 		}
 		return false;
 	}
 private:
 	int m_num;
 };
    
    
 void test8()
 {
 	vector<int>  v1;
 	for (int i = 0; i < 5; i++)
 	{
 		v1.push_back(i + 1);
 	}
    
 	for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++)
 	{
 		cout << *it << " ";
 	}
 	//3的个数
 	int num1 = count(v1.begin(), v1.end(), 3);
 	cout << "num1:" << num1 << endl;
    
 	//通过谓词求大于2的个数
 	int num2 = count_if(v1.begin(), v1.end(), IsGreat(2));
 	cout << "num2:" << num2 << endl;
    
 	//通过预定义函数对象，求大于2的个数   
 	//greater<int>() 有2个参数 ，通过bind2nd可以转化成一个参数的函数，另外一个参数绑定成2
 	int num3 = count_if(v1.begin(), v1.end(), bind2nd(greater<int>(), 2));
 	cout << "num3:" << num3 << endl;
    
 	//取模 能被2整除的数 求奇数
 	int num4 = count_if(v1.begin(), v1.end(), bind2nd(modulus <int>(), 2));
 	cout << "奇数num4:" << num4 << endl;
    
 	int num5 = count_if(v1.begin(), v1.end(), not1(bind2nd(modulus <int>(), 2)));
 	cout << "偶数num5:" << num5 << endl;
 	return;
 }

STL的容器算法迭代器的设计理念

pic-w50

  1. STL的容器通过类模板技术，实现数据类型和容器模型的分离
    1. 一种容器可以存放不同的数据类型
  2. STL的迭代器技术实现了遍历容器的统一方法；也为STL的算法提供了统一性奠定了基础
  3. STL的算法，通过函数对象实现了数据类型和算法的分离；所以说：STL的算法也提供了统一性。
    1. 函数对象分为2种：自定义、STL预定义
    2. 核心思想：其实函数对象本质就是回调函数，回调函数的思想：就是任务的编写者和任务的调用者有效解耦合。函数指针做函数参数。
  4. 具体例子：transform算法的输入，通过迭代器first和last指向的元算作为输入；通过result作为输出；通过函数对象来做自定义数据类型的运算。

All content is licensed under CC BY-NC-SA

Buit with Jekyll and 3-Jekyll theme • Hosted on Github

Table of Contents