[数据结构与算法]【STL算法】for_each源码刨析及函数对象本质刨析

文章目录

前言

本文中将通过STL中的for_each算法为例来深度分析函数对象的本质，以及如何通过分析STL源码来学习STL中的容器、迭代器和算法。

提示：下面将通过编程实战手把手教学如何通过分析源码来学习算法并写出自己的函数对象。

一、搭建一个测试框架

使用STL中的算法要包含头文件<algorithm>，下面搭建一个测试案例，创建一个int型的vector数组，并装入10个随机数，然后自己实现一个遍历容器的函数，对定义好的容器进行遍历打印。

代码如下：

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

void print_vector_int(vector<int>& v)
{
	//for(vector<int>::iterator it = v.begin(); it != v.end(); it++)
	//{
	//	cout << *it << " ";
	//}
	for (unsigned int i = 0; i < v.size(); i++)
	{
		cout << v.at(i) << " ";
	}
	cout << endl;
}

int main()
{
	vector<int> V;
	for (int i = 0; i < 10; i++)
	{
		V.push_back(rand());
	}
	print_vector_int(V);
    system("pause");
	return 0;
}

二、分析for_each源码

1.分析for_each的函数参数和返回值

一个函数最重要的就是他的参数和返回值，分析函数的参数和返回值是深刻理解这个函数功能的重要前提。我们可以通过VS的转到定义功能来查看for_each函数的原型，代码如下：

template <class _InIt, class _Fn>
	_Fn for_each(_InIt _First, _InIt _Last, _Fn _Func) { // perform function for each element [_First, _Last)
		_Adl_verify_range(_First, _Last); 
		auto _UFirst      = _Get_unwrapped(_First); 
		const auto _ULast = _Get_unwrapped(_Last); 
		for (; _UFirst != _ULast; ++_UFirst) { 
			_Func(*_UFirst); 
		}

		return _Func; //返回函数对象
	}

通过源码可以看出，这个函数有三个参数，第一个第二个参数应该是一个迭代器，第三个参数是一个函数对象（根据template后面的类型说明可以看出）。那么我们应该先定义一个函数对象，然后传入for_each实现功能。

既然要定义函数对象，根据我们前一篇文章的分析，函数对象就是一个重载了函数调用操作符（）的类，不了解的请查看

【STL实用技巧】函数对象（仿函数）与pair类型初探https://blog.csdn.net/qq_43471489/article/details/123610612?spm=1001.2014.3001.5501首先我们应该定义一个类，并在类中实现函数调用操作符（）的重载，这就涉及到我们的重载函数的接口应该是什么样子的，包括返回值、参数。根据函数重载的知识我们知道，返回值不是判断函数重载的标准，函数重载是根据函数参数的类型、个数、顺序等来决定的。也就是说函数重载的判断标准只与参数有关，因此，我们在重载函数调用操作符时应该重点关注函数参数。

我们要知道，类中重载的函数调用操作符（）是在for_each中使用的，所以，要想知道重载函数的原型，我们应该去for_each源码中去分析，我们看for_each源码的return前一句

_Func(*_UFirst);

for_each函数内部把一个*变量传给了函数对象，由此可见，我们重载的函数调用操作符函数应该只有一个参数。下面在分析这个参数的类型，我们继续看源码

auto _UFirst      = _Get_unwrapped(_First); 
const auto _ULast = _Get_unwrapped(_Last);

从这里可以看出，_UFirst应该是一个指针，它指向了迭代器_First的位置，那么*_UFirst就是对指针解引用，他应该是容器中的元素（迭代器所指向的元素），也就是说我们需要重载的函数的参数类型是容器的元素的类型。这样我们就确定好了重载函数的参数。

通过for_each源码分析可知，在for_each内部并没有用到_Func（也就是函数对象）的返回值，我们可以把它定义为void类型，这样我们需要重载的函数调用操作符的函数接口就有了。

2.定义函数对象

根据重载函数接口

void operator()(_Type t); //_Type和容器元素类型有关

我们可以定义一个类，并重载括号操作符，实现对容器元素+1的操作，另外在遍历容器的时候记录容器元素个数

template<typename _MyType>
class MySort
{
public:
	MySort()
	{
		this->m_count = 0;
	}
public:
	void operator()(_MyType& t) //怎么确定这个函数对象的参数呢？
	{
		t++;
		this->m_count++;
	}
public:
	int get_count()
	{
		return m_count;
	}
private:
	int m_count; //记录容器中元素个数
};

这样，使用for_each的时候，容器中每个变量都会进入这个仿函数，通过私有属性m_count就可以记录总共调用了仿函数多少次，也就是容器中元素的个数。

这里有一点要注意，就是为什么要自定义一个无参构造函数并将私有属性m_count置为0，如果我们不这么做的话，当我们使用类MySort定义对象的时候，编译会报错。

MySort m_sort1;

//错误	C4700	使用了未初始化的局部变量“m_sort1”	

这样我们便可以在主函数中添加以下代码进行测试

for_each(V.begin(), V.end(), MySort<int>()); //使用匿名函数对象
print_vector_int(V);

编译运行，可以看到功能已经实现。

3.for_each函数的返回值

在前面定义类的时候我们定义了一个私有属性m_count来记录容器元素个数，那么我们继续添加以下代码进行测试

MySort<int> m_sort1; //MySort有私有变量m_count，所以需要提供构造函数初始化m_count
for_each(V.begin(), V.end(), m_sort1);
cout << "计数：" << m_sort1.get_count() << endl;
print_vector_int(V);

并编译运行，查看打印结果

?我们看到计数值显示0，这和我们定义的10个元素的容器不符，那么问题出现在哪呢，我们继续看for_each的接口原型

_Fn for_each(_InIt _First, _InIt _Last, _Fn _Func)

问题就出现在这里，函数参数_Func是一个_Fn类型的元素，我们传进的实参m_sort1也是一个元素，但是实参和形参是两个不同的元素，我们把实参m_sort1复制给了形参_Func，在for_each函数内部对形参_Func的属性m_count进行了++运算，但是这和实参m_sort1毫无关系，实参m_sort1的m_count还是0。

注：实参和形参是两个完全不同的变量，在函数调用的时候只是把实参复制给了形参，实参还是实参，形参就是形参，他们两个没有任何关系。要想通过函数参数（形参）改变实参，就要使用引用或者指针（指针做函数参数间接修改实参）。

那么我们怎么使用m_count这个私有属性来打印容器元素个数呢，继续看源码，看for_each函数的返回值

return _Func;

for_each的返回值是一个_Fn 类型的_Func，也是函数的参数_Func。也就是说，形参通过返回值的形式被for_each函数返回了出来，那么我们便可以这么用，继续添加如下代码

MySort<int> m_sort2; 
m_sort2 = for_each(V.begin(), V.end(), m_sort2);
cout << "计数：" << m_sort2.get_count() << endl;
print_vector_int(V);

编译运行

我们看到，计数为10，与容器内元素个数相同。

这里应注意，我们用m_sort2来接for_each的返回值时，因为for_each返回的是一个元素，他会把这个元素复制给m_sort2并调用拷贝构造函数，因为我们的类中没有指针，不涉及深拷贝浅拷贝问题，所以不必写深拷贝构造函数，使用默认的浅拷贝构造函数即可。但是，如果类中有指针等涉及深拷贝问题的情况时，一定要手动实现深拷贝构造函数。?

4.for_each源码浅析

最后附上本人对for_each源码的理解，解析在代码注释中。

template <class _InIt, class _Fn>
_Fn for_each(_InIt _First, _InIt _Last, _Fn _Func) { // perform function for each element [_First, _Last)
	_Adl_verify_range(_First, _Last); //范围：容器迭代器 begin 到 end
	auto _UFirst      = _Get_unwrapped(_First); //指针_UFirst指向迭代器_First的位置
	const auto _ULast = _Get_unwrapped(_Last); //指针_ULast迭代器_Last的位置
	for (; _UFirst != _ULast; ++_UFirst) { //遍历容器
		_Func(*_UFirst); //把容器元素逐个放入函数_Func作为其函数参数
	}

	return _Func; //返回函数对象
}

三、函数对象的本质

1.函数对象的回调行为

通过上面的讲解，已经实现了自己的函数对象，那么函数对象到底是什么呢？

首先函数对象是一个类对象，它是一个重载了函数调用操作符的类所定义的对象。这个类中必须包含函数调用操作符（）的重载，其次它可以有自己的成员属性和成员方法，比如，上面我们定义的类中除了有函数调用操作符的重载，还有私有属性m_count和成员方法get_count()。

在for_each中对函数对象的使用上来看，我们不难发现，函数对象的行为很像一个函数，确切的说很像一个回调函数（C语言中函数指针做函数参数），所以它也叫仿函数。下面我们用一个普通函数来做for_each的参数，测试我们的猜想。

首先，定义一个模板函数

template<typename T>
void my_add(T& t)
{
	t++;
}

我们把这个函数做参数，并在main函数中继续添加如下测试代码

for_each(V.begin(), V.end(), my_add<int>);
print_vector_int(V);

编译运行，查看打印结果

?可以看到，通过普通的模板函数，我们也实现了函数对象的功能，对容器中每个元素遍历并加1。由此可见，函数对象确实和回调函数有着类似的功能。

C语言回调函数可以参考我的文章

【C语言实现多态效果实例】https://blog.csdn.net/qq_43471489/article/details/123364804

2.函数对象和回调函数的区别

既然回调函数和函数对象可以实现相同的功能，那么为什么要用函数对象呢？

首先，我们知道，函数对象是一个重载了()操作符的类所定义的对象，既然是类对象，那么他便可以拥有自己的属性和方法。就像前面我们通过类的私有属性m_count来计数容器中的元素个数，并通过成员函数get_count()来返回私有属性m_count。类中可以封装属性和方法，通过类对象做函数参数可以把属性和方法一块传入调用函数中，这是普通函数所不具备的。

四、完整代码

最后附上完整代码

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

void print_vector_int(vector<int>& v)
{
	//for(vector<int>::iterator it = v.begin(); it != v.end(); it++)
	//{
	//	cout << *it << " ";
	//}
	for (unsigned int i = 0; i < v.size(); i++)
	{
		cout << v.at(i) << " ";
	}
	cout << endl;
}

template<typename _MyType>
class MySort
{
public:
	MySort()
	{
		this->m_count = 0;
	}
public:
	void operator()(_MyType& t) //怎么确定这个函数对象的参数呢？
	{
		t++;
		this->m_count++;
	}
public:
	int get_count()
	{
		return m_count;
	}
private:
	int m_count; //记录容器中元素个数
};

template<typename T>
void my_add(T& t)
{
	t++;
}

int main()
{
	vector<int> V;
	for (int i = 0; i < 10; i++)
	{
		V.push_back(rand());
	}
	print_vector_int(V);

	/*
	template <class _InIt, class _Fn>
	_Fn for_each(_InIt _First, _InIt _Last, _Fn _Func) { // perform function for each element [_First, _Last)
		_Adl_verify_range(_First, _Last); //范围：容器迭代器 begin 到 end
		auto _UFirst      = _Get_unwrapped(_First); //指针_UFirst指向迭代器_First的位置
		const auto _ULast = _Get_unwrapped(_Last); //指针_ULast迭代器_Last的位置
		for (; _UFirst != _ULast; ++_UFirst) { //遍历容器
			_Func(*_UFirst); //把容器元素逐个放入函数_Func作为其函数参数
		}

		return _Func; //返回函数对象
	}
	*/
	for_each(V.begin(), V.end(), MySort<int>()); //匿名对象
	print_vector_int(V);
	
	MySort<int> m_sort1; //MySort有私有变量m_count，所以需要提供构造函数初始化m_count
	for_each(V.begin(), V.end(), m_sort1);
	cout << "计数：" << m_sort1.get_count() << endl;
	print_vector_int(V);
	
	MySort<int> m_sort2; //MySort有私有变量m_count，所以需要提供构造函数初始化m_count
	m_sort2 = for_each(V.begin(), V.end(), m_sort2);
	cout << "计数：" << m_sort2.get_count() << endl;
	print_vector_int(V);
	
	for_each(V.begin(), V.end(), my_add<int>);
	print_vector_int(V);
	
	system("pause");
	return 0;
}

总结

学习STL最好的教材就是源码，通过分析源码可以深刻理解STL容器、迭代器和算法的精髓。参考源码，才能写出我们自己的、编译器认可的、规范的代码。