【STL终极奥义❀解耦合思想的实现❀】函数对象、谓词与函数适配器——从for_each、transform、count_if、sort算法源码的角度分析(一)

简介: 【STL终极奥义❀解耦合思想的实现❀】函数对象、谓词与函数适配器——从for_each、transform、count_if、sort算法源码的角度分析

一、概念解析

  • 算法:STL提供的算法主要包含两大类,一类是不改变所操作容器内容的算法比如计数、搜索、比较等算法;另一类是修改所操作容器内容的算法,比如排序、删除等等。使用STL算法需要包含头文件。
  • 函数对象:函数对象是指重载了函数调用操作符()的类,其功能类似于回调函数,函数对象一般用于STL算法中来自定义回调行为。
  • 一元函数对象:重载的operator()函数只有一个参数;
  • 二元函数对象:重载的operator()函数有两个参数;
  • 谓词:谓词可以是仿函数(函数对象),也可以是回调函数,它的返回值是bool类型,作为一个判断式。
  • 一元谓词,只有一个参数的谓词;
  • 二元谓词:含有两个参数的谓词;
  • 函数适配器 :有时候算法中的函数对象只接收一元函数对象,但是我们想要实现的功能需要二元函数对象完成,这时我们就可以通过绑定器把一个二元函数对象和一个参数绑定在一起,适配成一元函数对象。使用函数适配器需要包含头文件。
  • 预定义函数对象:STL标准模板库已经提前预定义好的函数对象,比如greater、less等,使用预定义函数对象需要包含头文件。

二、从源码到实战

1. for_each算法与一元函数对象

本节目标是使用for_each算法实现遍历容器

1.1 搭建测试框架

搭建一个测试框架

1. #include <iostream>
2. using namespace std;
3. 
4. #include <vector>
5. #include <string>
6. #include <algorithm> //使用算法
7. #include <functional> //使用预定义函数对象和适配器
8. 
9. int main()
10. {
11.   vector<string> v1;
12.   v1.push_back("hello");
13.   v1.push_back("C++");
14.   v1.push_back("STL");
15.   v1.push_back("!");
16.   v1.push_back("!");
17.   v1.push_back("!");
18. 
19. /*在此添加测试代码*/
20. 
21.   system("pause");
22.   return 0;
23. }

1.2 for_each源码分析

首先转到for_each算法源码

1. _Fn for_each(_InIt _First, _InIt _Last, _Fn _Func) { // perform function for each element [_First, _Last)
2.    _Adl_verify_range(_First, _Last);
3.    auto _UFirst = _Get_unwrapped(_First);
4.    const auto _ULast = _Get_unwrapped(_Last);
5.    for (; _UFirst != _ULast; ++_UFirst) {
6.      _Func(*_UFirst); //通过源码可知,for_each 的函数对象是一元函数对象
7.    }
8. 
9.    return _Func;
10.   }

根据源码分析可知,for_each算法接收一个一元函数对象,并返回该对象,它会把传入的容器中的元素一个个的放入回调函数_Func作为函数参数。由此可见,for_each只是提供了一个壳子,这个壳子的功能是把一个容器的所有元素(起始和结束都有我们通过迭代器传入)依次作为参数传给函数对象_Func,而具体对这些元素做什么操作,由我们自己通过回调函数_Func实现。这就是算法统一性和解耦合思想的体现。

1.3 根据for_each源码实现一元函数对象

根据源码可以分析出回调函数的接口,一个参数,无返回值(或未用到返回值)。

1. //一元函数对象
2. template<typename _MyType>
3. class _FroEachClass
4. {
5. public:
6.  void operator()(_MyType& t)
7.  {
8.    cout << t << " ";
9.    m_count++;
10.   }
11. public:
12.   _FroEachClass()
13.   {
14.     this->m_count = 0;
15.   }
16. public:
17.   int get_count()
18.   {
19.     return this->m_count;
20.   }
21. private:
22.   int m_count;
23. };
24. 
25. template<typename _MyType>
26. void _FroEachFunc(_MyType& t)
27. {
28.   cout << t << " ";
29. }

回调函数和函数对象(类)的区别已经在另一篇文章中分析过了,函数对象可以有自己的属性和方法,因为类的封装特性,可以把属性方法一并传入作为函数参数,详情可见

【STL算法】for_each源码刨析及函数对象本质刨析https://blog.csdn.net/qq_43471489/article/details/123633464?spm=1001.2014.3001.5501我们在主函数添加如下测试代码

1. _FroEachClass<string> for_each_obj;
2. for_each_obj = for_each(v1.begin(), v1.end(), for_each_obj);
3. cout << "\nvector size: " << for_each_obj.get_count() << endl;
4. for_each(v1.begin(), v1.end(), _FroEachFunc<string>);
5. cout << endl;

编译运行

可以看到,使用函数对象和回调函数都能实现遍历容器,使用函数对象可以通过私有属性记录容器中元素个数。

2. count_if算法与一元谓词

本节目标是使用count_if算法计算某个元素的个数

2.1 count_if源码分析

通过VS转到源码功能

1. template <class _InIt, class _Pr>
2. _NODISCARD _Iter_diff_t<_InIt> count_if(_InIt _First, _InIt _Last, _Pr _Pred) { // count elements satisfying _Pred
3.  _Adl_verify_range(_First, _Last);
4.  auto _UFirst = _Get_unwrapped(_First);
5.  const auto _ULast = _Get_unwrapped(_Last);
6.  _Iter_diff_t<_InIt> _Count = 0;
7.  for (; _UFirst != _ULast; ++_UFirst) {
8.    if (_Pred(*_UFirst)) { //由此可见_Pred返回的应该是一个bool
9.      ++_Count;
10.     }
11.   }
12. 
13.   return _Count;
14. }

通过源码分析可知,count_if算法提供了这样一个壳子,他会把我们传入的容器迭代器范围内的元素依次传递给函数对象_Pred,并且函数对象_Pred返回一个bool类型,由此可知count_if的参数是一个一元谓词

if (_Pred(*_UFirst)) { //由此可见_Pred返回的应该是一个bool

如果这个返回结果为真,即传递给函数对象_Pred的参数(容器元素)符合条件,就进行一次计数。最终count_if返回这个计数值。

2.2 根据count_if源码实现一元谓词

根据上一小节分析可知,我们要写的谓词接口形式为bool类型返回值,一个参数,代码如下:

1. template<typename _MyType>
2. class _CountOfClass
3. {
4. public:
5.  bool operator()(_MyType& t)
6.  {
7.    return (t == this->m_data);
8.  }
9. public:
10.   _CountOfClass(_MyType& t)
11.   {
12.     this->m_data = t;
13.   }
14. private:
15.   _MyType m_data;
16. };
17. 
18. template<typename _MyType>
19. bool _CountOfFunc(_MyType& t1)
20. {
21.   string s = "!";
22.   return (t1 == s);
23. }

然后再主函数继续添加如下测试代码,我们使用count_if计算容器中“!”出现的次数

1. string s("!");
2. int count = count_if(v1.begin(), v1.end(), _CountOfClass<string>(s));
3. cout << "count : " << count << endl;
4. count = count_if(v1.begin(), v1.end(), _CountOfFunc<string>); //使用回调函数也可以编译通过
5. cout << "count : " << count << endl;

编译运行

通过运行结果看到,容器中总共3个叹号。

3. transform算法与二元函数对象

本节目标,使用transform算法实现把两个容器内容相加放入第三个容器。

3.1 transform源码分析

使用VS查看源码

1. template <class _InIt1, class _InIt2, class _OutIt, class _Fn>
2. _OutIt transform(const _InIt1 _First1, const _InIt1 _Last1, const _InIt2 _First2, _OutIt _Dest, _Fn _Func) {
3.    // transform [_First1, _Last1) and [_First2, ...) with _Func
4.  _Adl_verify_range(_First1, _Last1);
5.  auto _UFirst1 = _Get_unwrapped(_First1);
6.  const auto _ULast1 = _Get_unwrapped(_Last1);
7.  const auto _Count = _Idl_distance<_InIt1>(_UFirst1, _ULast1);
8.  auto _UFirst2 = _Get_unwrapped_n(_First2, _Count);
9.  auto _UDest = _Get_unwrapped_n(_Dest, _Count);
10.   for (; _UFirst1 != _ULast1; ++_UFirst1, (void) ++_UFirst2, ++_UDest) {
11.     *_UDest = _Func(*_UFirst1, *_UFirst2); //把两个参数_UFirst1和_UFirst2的元素传入_Func返回结果放入_UDest
12.   }
13. 
14.   _Seek_wrapped(_Dest, _UDest);
15.   return _Dest;
16. }

这只是transform算法的一个重载模型之一,首先传入参数是两个容器的输入迭代器_First1、_Last1、_First2,其中第一个容器给出了起始和结束位置的迭代器,用来限定操作的容器范围,输出迭代器_Dest。通过这条语句可以看到

*_UDest = _Func(*_UFirst1, *_UFirst2); //把两个参数_UFirst1和_UFirst2的元素传入_Func返回结果放入_UDest

transform算法把两个输入迭代器指示的容器元素传入回调函数_Func作为参数,并返回一个元素装入到输出迭代器_Dest所指示的容器位置中。由此分析可知,transform算法提供了这样一个模型,把两个容器中的元素进行操作,操作结果存放到第三个容器中,所以_Func的返回值应该是和容器类型同类型的一个元素,操作的元素个数由第一个容器的迭代器指定,最终transform返回第三个容器的迭代器位置。transform需要的是一个二元函数对象。


目录
打赏
0
0
0
0
13
分享
相关文章
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
Java中的算法优化与复杂度分析
在Java开发中,理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略,可以显著提高算法效率。在实际开发中,应该根据具体需求和场景,选择合适的优化方法,从而编写出高效、可靠的代码。
56 6
婚恋交友系统平台 相亲交友平台系统 婚恋交友系统APP 婚恋系统源码 婚恋交友平台开发流程 婚恋交友系统架构设计 婚恋交友系统前端/后端开发 婚恋交友系统匹配推荐算法优化
婚恋交友系统平台通过线上互动帮助单身男女找到合适伴侣,提供用户注册、个人资料填写、匹配推荐、实时聊天、社区互动等功能。开发流程包括需求分析、技术选型、系统架构设计、功能实现、测试优化和上线运维。匹配推荐算法优化是核心,通过用户行为数据分析和机器学习提高匹配准确性。
187 3
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
99 1
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
193 7
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
159 8
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
基于遗传优化算法的风力机位置布局matlab仿真
本项目基于遗传优化算法(GA)进行风力机位置布局的MATLAB仿真,旨在最大化风场发电效率。使用MATLAB2022A版本运行,核心代码通过迭代选择、交叉、变异等操作优化风力机布局。输出包括优化收敛曲线和最佳布局图。遗传算法模拟生物进化机制,通过初始化、选择、交叉、变异和精英保留等步骤,在复杂约束条件下找到最优布局方案,提升风场整体能源产出效率。
基于包围盒的机械臂防碰撞算法matlab仿真
基于包围盒的机械臂防碰撞算法通过构建包围盒来近似表示机械臂及其环境中各实体的空间占用,检测包围盒是否相交以预判并规避潜在碰撞风险。该算法适用于复杂结构对象,通过细分目标对象并逐级检测,确保操作安全。系统采用MATLAB2022a开发,仿真结果显示其有效性。此技术广泛应用于机器人运动规划与控制领域,确保机器人在复杂环境中的安全作业。

热门文章

最新文章