13.6.2　算法分类

    STL将算法库分为4组，前3个在algorithm头文件中进行描述，而第4个在numeric头文件中进行描述，如下所述。

    ❑非修改式序列操作，不可以改变容器的内容，如find（）和for_each（）等。

    ❑修改式序列操作，可以修改容器中的内容，如transform（）、random_shuffle（）和copy等。

    ❑排序和相关操作，包括各种排序函数等，如sort（）等。

    ❑通用数字运算，计算两个容器的内部乘积等。

    STL中算法函数太多，无法一一进行介绍，本节先以简表的形式列举出常用的算法。

    1.非修改式序列操作

    非修改式序列操作函数如表13.9所示，因为参数的形式相对复杂，表中只列举了函数模板名，具体的应用方式可查阅STL的相关资料。

    13.6.2 算法分类 - 图1

    13.6.2 算法分类 - 图2

    以for_each函数为例，其原型如下所示。

    template＜class InputInterator,class Function＞ Function for_each（InputIterator First,InputIterator Last,Function f）；

    将一个非修改式函数对象f用于这个区间[First,Last）中的每个成员，其中函数对象f为一元函数，参数为容器对象元素或元素的引用，for_each函数的使用范例如代码13.16所示。

    代码13.16　for_each函数的用法ForEach

    ＜————————————文件名：example1316.cpp——————————————-＞ 01　#include＜iostream＞ 02　#include＜algorithm＞//使用for_each函数要包含的头文件 03　#include＜vector＞ 04　using namespace std； 05　typedef vector＜int＞VI； 06　typedef VI：iterator VIP； 07　void func（VI：value_type v）//定义1个原函数func，以元素类型为参数 08　{ 09　cout＜＜v＜＜""； 10　} 11　int main（） 12　{ 13　int sz[]={1，2，3，4，5，6}； 14　VI ob（sz,sz+6）； 15　for_each（ob. begin（），ob.end（），func）；//对ob中所有元素执行func操作 16　cout＜＜endl； 17　return 0； 18　}

    输出结果如下所示。

    1 2 3 4 5 6

    【代码解析】代码第7行的func函数是一个函数对象，定义了对ob中元素的操作，for_each函数用于对ob中所有元素执行func操作。

    2.修改式序列操作

    STL中提供了很多序列操作函数，表13.10列举了函数模板名，具体的应用方式可查阅STL的相关资料。

    13.6.2 算法分类 - 图3

    3.排序和相关操作

    表13.11列举排序及其相关操作的函数模板名，具体的应用方式可查阅STL的相关资料。

    13.6.2 算法分类 - 图4

    以replace_if（）为例，其原形如下所示。

    template＜class InputIterator,class Predict,class T＞ void replace_if（Forward Iterator First,ForwardIterator Last,Predicate pred,const T＆new）；

    如果区间[First,Last）中的元素使得元素pred返回true，则将该元素用new替换，否则不予替换，如代码13.17所示。

    代码13.17　replace_if函数使用方法ReplaceIf

    ＜———————————文件名：example1317.cpp———————————————-＞ 01　#include＜iostream＞ 02　#include＜algorithm＞//使用for_each函数要包含的头文件 03　#include＜functional＞//使用less＜＞类模板要用的头文件 04　#include＜vector＞ 05　using namespace std； 06　typedef vector＜int＞VI； 07　typedef VI：iterator VIP； 08　int main（） 09　{ 10　int sz[]={1，2，3，4，5，6}； 11　VI ob（sz,sz+6）； 12　less＜int＞lt；//使用类模板less＜int＞创建函数对象 13　replace_if（ob. begin（），ob.end（），bind2nd（lt，3），7）； 14　for（VIP v=ob. begin（）；v！=ob.end（）；v++） 15　{ 16　cout＜＜（*v）＜＜""； 17　} 18　cout＜＜endl； 19　return 0； 20　}

    输出结果如下所示。

    7 7 3 4 5 6

    【代码解析】代码第12行使用类模板less＜int＞创建的函数对象it是二元断言，而replace_if函数中要使用的是一元断言，因此必须为it提供一个接口，使其可以用在replace_if函数中，为了将it转化成一元断言，代码13.17使用了“将it的第2个数据绑定为用户指定的数值3”的方法，即如果ob中的元素小于3，则返回true，该元素替换为7，否则不执行替换。

    这种转换的思路便是适配器（Adapter）思想，稍后详细介绍适配器。

    4.数字操作

    表13.12列举了的是STL提供的数字和计算函数模板。

    13.6.2 算法分类 - 图5