C++，STL -- 函数对象、常用算法

布满荆棘的人生 2024-03-25 21:40 45阅读 0赞

#### STL -- 函数对象、常用算法 ####

*   *  STL — 函数对象
     *   *  函数对象
         *  谓词
         *  内建函数对象
     *  STL — 常用算法
     *   *  1. 常用遍历算法
         *  2. 常用查找算法
         *  3. 常用排序算法
         *  4. 常用拷贝和替换算法
         *  5. 常用算数生成算法
         *  6. 常用集合算法

[C++ 模板][C_]  
[STL常用容器][STL]

### STL — 函数对象 ###

#### 函数对象 ####

**1. 函数对象概念**

**概念:**

*  重载**函数调用操作符**的类，其对象常称为**函数对象**
 *  **函数对象**使用重载的`()`时，行为**类似函数调用**，也叫 **仿函数**

**本质:**

*  **函数对象**(仿函数)是一个 **类**，不是一个函数

**2. 函数对象使用**

**特点:**

1.  函数对象在使用时，可以**像普通函数那样调用**, **可以有参数**，**可以有返回值**

//仿函数
    class MyAdd
    {
        
    public:
    	int operator()(int vl, int v2)
    	{
        
    		return vl + v2;
    	}
    };
    //调用
    void test01()
    {
        
    	MyAdd myAdd;
    	cout << myAdd(10, 10) << endl;
    }

1.  函数对象超出普通函数的概念，函数对象**可以有自己的状态**

//仿函数
    class MyPrint(
    public:
    	MyPrint()
    	{
        
    		this->count = 0;
    	}
    	void operator() (string test)
    	{
        
    		cout << test << endl;
    		this->count++;
    	}
    	int count; //内部自己状态
    };
    
    //调用
    void test02()
    {
        
    	MyPrint myPrint;
    	myPrint("hello world");
    	myPrint("hello world");
    	myPrint("hello world");
    	myPrint("hello world");
    
    	cout << "myPrint调用次数为:"<< myPrint.count << endl;
    }

1.  函数对象可以作为**参数传递**

void doPrint(MyPrint & mp, string test)
    {
        
    	mp(test);
    }
    void test03()
    {
        
    	MyPrint myPrint;
    	doPrint(myPrint, "Hello c++");
    }

#### 谓词 ####

**1. 谓词概念**

**概念:**

*  返回`bool`类型的**仿函数**称为 **谓词**
 *  如果operator()接受**一个参数**，那么叫做**一元谓词**
 *  如果operator()接受**两个参数**，那么叫做**二元谓词**

**2. 一元谓词**

//仿函数
    class GreaterFive{
        
    public:
    	bool operator() (int val)
    	{
        
    		return val > 5;
    	}
    };
    
    void test01()
    {
        
    	vector<int>v;
    	for(int i = 0; i < 10; i++)
    	{
        
    		v.push_back(i);
    	}
    	
    	//查找容器中有没有大于5的数字
    	//GreaterFive() 匿名函数对象
    	vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
    	if(it == v.end()){
        
    		cout <<"未找到"<< endl;
    	}
    	else
    	{
        
    		cout << "找到了大于5的数字为:" << *it << endl;
    	}
    }

**3. 二元谓词**

//仿函数
    class MyCompare
    {
        
    public:
    	bool operator() (int val1, int val2)
    	{
        
    		return val1 > val2;
    	}
    }
    
    void test02()
    {
        
    	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());
    	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    	{
        
    		cout<< *it <<" ";
    	}
    	cout << endl;
    	
    	//使用函数对象改变算法策略，变为排序规则为从大到小,MyCompare()为匿名函数对象
    	sort(v.begin(), v.end(), MyCompare());
    	cout<< "---------—---"<<endl;
    	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    	{
        
    		cout<< *it <<" ";
    	}
    	cout << endl;
    }

#### 内建函数对象 ####

**概念:**

*  STL**内建**了一些**函数对象**

**分类:**

*  **算术**仿函数
 *  **关系**仿函数
 *  **逻辑**仿函数

**用法:**

*  这些仿函数所产生的对象，用法和一般函数完全相同
 *  使用内建函数对象，需要引入**头文件**`#include<functional>`

**1. 算数仿函数**

**功能描述:**

*  实现四则运算
 *  其中`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>              //取反仿函数

**使用：**

#include <functional> //内建函数对象头文件
    
    negate<int>n;
    cout << n(50) << endl ;
    
    plus<int>p;
    cout << p(10, 20)<< endl;

**2. 关系仿函数**

**功能描述:**

*  实现关系**对比**

**仿函数原型:**

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>                      //小于等于

**使用：**

//包含头文件
    #include <algorithm>
    #include<functional>
    
    //降序
    //greater<int>() 内建函数对象
    sort(v.begin, v.end(), greater<int>());

**3. 逻辑仿函数**

**功能描述:**

*  实现逻辑运算

**函数原型:**(在实际开发中，很少使用)

template<class T> bool logical_and<T>				//逻辑与
    template<class T> bool logical_or<T>				//逻辑或
    template<class T> bool logical_not<T>				//逻辑非

**使用：**

//包含头文件
    #include <algorithm>
    #include<functional>
    
    …
    
    //利用逻辑非将容器v搬运到容器v2中,并执行取反操作vector<boo1>v2;
    v2.resize(v.size()); //搬运前先指定大小
    transform(v.begin(), v.end(), v2.begin(), logical_not<bool>());

> **总结:** 逻辑仿函数实际应用较少，了解即可~

### STL — 常用算法 ###

**概述:**

*  算法主要是由头文件`<algorithm>` `<functional>` `<numeric>`组成。
 *  `<algorithm>` 是所有STL头文件中最大的一个，范围涉及到**比较**、**交换**、**查找**、**遍历操作**、**复制**、**修改**等等
 *  `<numeric>`体积很小，只包括几个在序列上面进行**简单数学运算的模板函数**
 *  `<functional>`定义了一些模板类,用以声明**函数对象**。

#### 1. 常用遍历算法 ####

**算法简介:**

#include<algorithm>
    
    for_each                                 //遍历容器
    transform                                //搬运容器到另一个容器中

**1.1、for\_each**

**功能描述:**

*  实现**遍历容器**

**函数原型:**

for_each(iterator beg, iterator end, _func);          //遍历算法遍历容器元素
    // beg开始迭代器
    // end结束迭代器
    // _func函数或者函数对象

**使用：** `for_each` 在实际开发中是最常用遍历算法，需要熟练掌握

#include<iostream>
    using namespace std;
    #include<vector>
    #include<algorithm>
    
    
    //普通函数
    void print01(int val)
    {
        
    	cout << val << " ";
    }
    
    //仿函数
    class print02 
    {
        
    public:
    	void operator()(int val) {
        
    		cout << val << " ";
    	}
    };
    
    void test01() 
    {
        
    	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());
    	cout << endl;
    }
    int main()
    {
        
    	test01();
    
    	return 0;
    }

**1.2、 transform**

**功能描述:**

*  **搬运容器到另—个容器中**

**函数原型:**

transform(iterator beg1, iterator end1, iterator beg2, _func);        
    //beg1源容器开始迭代器
    //end1源容器结束迭代器
    //beg2目标容器开始迭代器
    //_func函数或者函数对象

**使用**

#include<iostream>
    using namespace std;
    #include<vector>
    #include<algorithm>
    
    //仿函数
    class MyPrint
    {
        
    public:
    	void operator()(int val) {
        
    		cout << val << " ";
    	}
    };
    
    class Transform
    {
        
    public:
    	int operator()(int v) 
    	{
        
    		return v + 100;//搬运前可以进行一些逻辑运算
    	}
    };
    
    void test02() 
    {
        
    	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());
    	cout << endl;
    
    	
    }
    int main()
    {
        
    	test02();
    
    	return 0;
    }

#### 2. 常用查找算法 ####

**算法简介:**

find							//查找元素
    find_if							//按条件查找元素
    adjacent_find					//查找相邻重复元素
    
    binary_search					//二分查找法
    
    count							//统计元素个数
    count_if						//按条件统计元素个数

**2.1、 find**

**功能描述:**

*  **查找指定元素**，找到返回指定元素的**迭代器**，找不到返回**结束迭代器** end()

**函数原型:**

find(iterator beg, iterator end, value);
    //按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
    //beg 开始迭代器
    //end结束迭代器
    //value查找的元素

查找**自定义数据类型**时，要**重载**`==`

class Person{
        
    public:
    	Person(string name, int age)
    	{
        
    		this->m_Name = name;
    		this->m_Age = age;
    	}
    	//重载==
    	bool operatcr==(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;
    };

查找自定义数据类型：

vector<Person>::iterator it = find(v.begin(),  v.end(),  p2);

**2.2、find\_if**

**功能描述:**

*  **按条件查找元素**

**函数原型:**

find_if(iterator beg, iterator end, _Pred);
    //按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
    //beg 开始迭代器
    //end 结束迭代器
    //_Pred 函数 或者 谓词（返回bool类型的仿函数)

> 总结:统计自定义数据类型时候，需要配合**重载** operator==

**2.3、 adjacent\_find**

**功能描述:**

*  **按条件统计**元素个数

**函数原型:**

count_if(iterator beg, iterator end, _Pred);
    //按条件统计元素出现次数
    // beg开始迭代器
    // end结束迭代器
    // _Pred谓词

**功能描述:**

*  查找 **相邻** **重复** 元素

> 例如：1252443, 返回 4

**函数原型:**

adjacent_find(iterator beg, iterator end) ;
    //查找相邻重复元素,返回相邻元素的第一个位置的迭代器
    //beg开始迭代器
    //end结束迭代器

> 总结:面试题中如果出现查找相邻重复元素，记得用STL中的adjacent\_find算法

**2.4、 binary\_search**

**功能描述:**

*  查找指定元素**是否存在**

**函数原型:**

bool binary_search(iterator beg, iterator end, value);
    //查找指定的元素，查到返回true否则false
    //注意:在无序序列中不可用
    // beg开始迭代器
    // end结束迭代器
    // value查找的元素

> 总结:二分查找法查找效率很高，值得注意的是查找的容器中元素必须的 **有序序列**

**2.5、 count**

**功能描述:**

*  **统计** **元素个数**

**函数原型:**

int count(iterator beg, iterator end, value);
    //统计元素出现次数I
    // beg 开始迭代器
    // end结束迭代器
    // value统计的元素

**2.6、 count\_if**

**功能描述:**

*  **按条件** **统计元素个数**

**函数原型:**

count_if(iterator beg, iterator end, _Pred);
    //按条件统计元素出现次数
    // beg 开始迭代器
    // end 结束迭代器
    //_Pred 谓词（返回bool类型的仿函数)

**定义年龄大于20的谓词**

class AgeGreater20{
        
    public:
    	bool operator()(const Person & p)
    	{
        
    		return p.m_Age > 20;
    	}
    };
    
    //使用
    int num = count_if(v.begin(), v.end(), AgeGreater20()) ;

#### 3. 常用排序算法 ####

**算法简介:**

sort               				//对容器内元素进行排序
    random_shuffle              	//洗牌指定范围内的元素随机调整次序
    merge              				//容器元素合并，并存储到另一容器中
    reverse              			//反转指定范围的元素

**3.1、 sort**

**功能描述:**

*  对**容器**内元素进行**排序**

**函数原型:**

sort(iterator beg, iterator end, _Pred);
    //对容器内元素进行排序
    // beg开始迭代器
    // end结束迭代器
    // _Pred谓词(不填，默认是从小到大排序)

**使用：**

#include<functional>
    
    //利用sort进行升序
    sort(v.begin(),  v.end()) ;
    
    //改变为降序,使用内建函数对象
    sort(v.begin(),  v.end, greater<int>());

> 总结: sort属于开发中最常用的算法之一，需熟练掌握

**3.2、 random\_shuffle**

**功能描述:**

*  **洗牌** 指定范围内的元素**随机调整次序**

**函数原型:**

random_shuffle(iterator beg, iterator end);
    //指定范围内的元素随机调整次序
    // beg开始迭代器
    // end结束迭代器

加上 **随机数种子**:

#include <ctime>
    
    srand ((unsigned int)time(NULL));//加上随机数种子，每次运行结果都不同
    
    //利用洗牌算法打乱顺序
    random_shuffle(v.begin(), v.end()) ;

> 总结: random\_shuffle洗牌算法比较实用，使用时记得加**随机数种子**

**3.3、 merge**

**功能描述:**

*  两个容器元素(都有序)**合并**，并**存储到另一容器中**

**函数原型:**

merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
    //容器元素合并，并存储到另一容器中
    //注意:两个容器必须是有序的
    // beg1容器1开始迭代器 
    // end1容器1结束迭代器
    // beg2容器2开始迭代器
    // end2容器2结束迭代器
    // dest目标容器开始迭代器

> 总结:merge合并的两个容器必须的**有序序列**

**3.4、reverse**

**功能描述:**

*  将容器内元素进行反转

**函数原型:**

reverse(iterator beg, iterator end);
    //反转指定范围的元素
    // beg 开始迭代器
    // end 结束迭代器

> 总结: reverse反转区间内元素，面试题可能涉及到

#### 4. 常用拷贝和替换算法 ####

**算法简介:**

copy						//容器内指定范围的元素拷贝到另—容器中
    replace						//将容器内指定范围的旧元素修改为新元素
    replace_if					//容器内指定范围满足条件的元素替换为新元素
    swap						//互换两个容器的元素

**4.1、copy**

**功能描述:**

*  容器内指定范围的元素 **拷贝** 到另—容器中

**函数原型:**

copy(iterator beg, iterator end,  iterator dest) ;
    //按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
    // beg开始迭代器
    // end 结束迭代器
    // dest目标起始迭代器

> 总结:利用copy算法在拷贝时，目标容器记得提前开辟空间

**4.2、replace**

**功能描述:**

*  将容器内指定范围的旧元素 **修改** 为新元素

**函数原型:**

replace(iterator beg, iterator end, oldvalue, newvalue);
    //将区间内旧元素替换成新元素
    // beg 开始迭代器
    // end 结束迭代器
    // oldvalue 旧元素
    // newvalue 新元素

**4.3、replace\_if**

**功能描述:**

*  将区间内**满足条件的元素**，**替换**成指定元素

**函数原型:**

replace_if(iterator beg, iterator end, _pred, newvalue);
    //按条件替换元素，满足条件的替换成指定元素
    // beg 开始迭代器
    // end 结束迭代器
    // _pred 谓词
    // newvalue 替换的新元素

谓词使用：

class Greater30
    {
        
    public:
    	bool operator()(int val)
    	{
        
    		return val >= 30;
    	}
    };
    
    //调用
    //将大于等于30替换为3000
    replace_if(v.begin(), v.end()， Greater30(), 3000);

> 总结: replace\_if 按条件查找，可以利用**仿函数**灵活筛选满足的条件!

**4.4、swap**

**功能描述:**

*  **互换** 两个容器(同种类型)的元素

**函数原型:**

swap(container c1, container c2);
    // 互换两个容器的元素
    // c1容器1
    // c2容器2

> 总结: swap交换容器时，注意交换的容器要同种类型

#### 5. 常用算数生成算法 ####

**算术生成算法属于小型算法**，使用时包含的 **头文件** 为 `#include <numeric>`

**算法简介:**

accumulate						//计算容器元素累计总和
    fill							//向容器中添加元素

**5.1、accumulate**

**功能描述:**

*  计算区间内容器元素**累计总和**

**函数原型:**

# include<numeric>
    int accumulate(iterator beg, iterator end, value);
    //计算容器元素累计总和
    // beg 开始迭代器
    // end 结束迭代器
    // value 起始值 ( 起始累加值，不想累加就赋 0 )

> 总结:accumulate使用时头文件注意是numeric，这个算法很实用

**5.2、fill**

**功能描述:**

*  向容器中**填充指定的元素**

**函数原型:**

fi1l(iterator beg, iterator end, value);
    //向容器中填充元素
    // beg 开始迭代器
    // end 结束迭代器
    // value 填充的值

> 总结:利用 fill 可以将容器区间内元素 **填充为指定的值**

#### 6. 常用集合算法 ####

**算法简介:**

set_intersection					//求两个容器的交集
    set_union						    //求两个容器的并集
    set_difference					    //求两个容器的差集

**6.1、set\_intersection**

**功能描述:**

*  求两个容器的 **交集**

**函数原型:**

//两个集合必须有序
    //返回指向所求交集的 （end）最后位置的迭代器
    set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
    //求两个集合的交集

> 总结: 求交集的两个集合必须的 **有序序列**

**6.2、set\_union**

**功能描述:**

*  求两个集合的 **并集**

**函数原型:**

//返回指向所求交集的 （end）最后位置的迭代器
    set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
    // 求两个集合的并集
    // 注意:两个集合必须是有序序列
    // beg1 容器1开始迭代器
    // end1 容器1结束迭代器
    // beg2 容器2开始迭代器
    // end2 容器2结束迭代器
    // dest 目标容器开始迭代器

**使用：**

vector<int>::iterator itEnd = set_unign(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
    
    for_each(vTarget.begin(), itEnd, myPrint);

> 总结:  
> 求并集的两个集合必须的**有序序列**  
> 目标容器**开辟空间需要两个容器相加**  
> set\_union返回值既是**并集中最后一个元素的位置**

**6.3、set\_difference**

**功能描述:**

*  求两个集合的**差集**

**函数原型:**

//返回指向所求交集的 （end）最后位置的迭代器
    set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
    //求两个集合的差集
    //注意:两个集合必须是有序序列
    // beg1容器1开始迭代器
    // end1容器1结束迭代器
    // beg2容器2开始迭代器
    // end2容器2结束迭代器
    // dest目标容器开始迭代器

> 总结:  
> 求差集的两个集簧必须的**有序序列**  
> 目标容器开辟空间需要从两**个容器取较大值**  
> set\_difference返回值既是**差集中最后一个元素的位置**

**注：仅供学习参考，如有不足，欢迎指正！**

[C_]: https://blog.csdn.net/weixin_43412762/article/details/129519442
[STL]: https://blog.csdn.net/weixin_43412762/article/details/129561216