天天看点

从零开始学C++之STL(五):非变动性算法源代码分析与使用示例( for_each、min_element 、find_if、search 等)

非变动性算法代码分析与示例:

一、for_each

函数以模板实现,_Inlt 即 iterator 类型,_Fn1 是函数指针,函数体内首先判断迭代器是否在范围内以及传递的第三个参数是否是函

数指针,接下去两行实际上就是定义两个临时的迭代器,相当于 _Inlt  ChkFirst(_First); 在遍历的过程中将每个容器元素取出并当作参

数传递给函数指针,即 _Func(*ChkFirst);  for_each 函数返回值是函数指针

二、max_element、min_element

两个函数实现差不多,只看min_element:

首先  #define _ASSIGN_FROM_BASE(_Dest, _Src)  _Dest = (_Src) 即将_Min_element 函数的返回值复制给_First,而在

_Min_element 函数内就是遍历容器,不断保存最小元素的位置,其中 #define _DEBUG_LT(x, y) ((x) < (y))   故

_DEBUG_LT(*_First, *_Found) 也就是取出元素比较大小,返回最后保存的最小元素位置。

实际上min_element 还重载了另一个函数模板:

主要的区别只是在于这个版本可以自定义进行比较,比如如果容器内不是装着数值元素,而是string 或者其他类型,也许它们没有重

载 operator<,可以自定义一个函数对它们进行比较大小,如 #define _DEBUG_LT_PRED(pred, x, y) pred(x, y) 就是这个意思。

三、find、find_if

里面很多宏跟前面函数出现的是一样的,find 就是遍历容器,找出与Val 相等的第一个元素位置,函数返回迭代器 。

find_if 则可以自定义查找,不一定是与某值相等,也可以其他比较如大于小于等,如 if (_Pred(*_First))  如果_Pred 函数返回为真

则break,至于_Pred 怎样实现就不关find_if 的事了。

示例代码1:

四、search

函数传入4个迭代器,假设前两个迭代器指示的位置有10个元素,后两个迭代器指示的位置有2个元素,如果在第一个区间能够找到

完全匹配第二个区间的元素,则返回起始位置,如果不能则返回Last1,即第一个区间末尾,注意必须顺序匹配2个元素,也可以看

成在第一个区间寻找第一次出现的第二个区间子段。

函数的实现也不难理解,双重循环,比如首先比较L1[0] 与 L2[0] , 如果相等再比较L1[1] 与 L2[1]; 如果不等则移动,从L1[1] 开始比

较,假设L1[4], L1[5] 与L2[0], L2[1] 完全匹配,则返回值是指向L1[4] 的 iterator。

此外seach 也重载了另一个版本,可以自定义比较,代码比较长且跟上面重复较多就不贴了,主要的变化就是将上面24行的代码

换成 else if (!_Pred(*_Mid1, *_Mid2)) 也就是自定义比较逻辑。

下面贴一个MSDN 的例子:

参考:

C++ primer 第四版

Effective C++ 3rd

C++编程规范