我的书签
添加书签
移除书签6.3 STL算法目录
这一部分为读者查找适当的算法提供快捷参考。而把所有的STL算法的完整探究以及问题更深层的细节如性能等一起作为其他参考材料（见本章结尾及附录A）。本节的目标是使读者能够快速熟悉这些算法，并且假定如果需要更多的细节将查找到更多特别指明的参考资料。
尽管读者经常见到用完整的模板声明语法来描述算法，但我们在这里不这样做，因为已经知道它们是模板，并且很容易知道函数声明中的模板参数是什么。参数的类型名为需要的迭代器类型提供描述。读者会发现，这种形式更容易读懂，如果需要，可以很快地在模板头文件中找到所有的声明。
所有涉及迭代器而令人心烦的原因，都是为了（使算法）适用于符合标准库要求的任意类型的容器。到目前为止，本章仅用数组和vector作为序列阐述了通用算法，但是在下一章中，读者将会看到一个范围更广的数据结构，这些数据结构支持只用较少力气进行迭代的工作。由于这个原因，将对算法进行部分地分类，这种分类按它们所需要的迭代类型很容易完成。
迭代器的类名描述必须与该迭代器的类型相符合。这些迭代器没有用接口基类来强化这些迭代运算—仅是期望它们在这里出现而已。如有没有接口基类，接收这样程序的编译器可能就会抱怨。下面简要地描述迭代器的各种形式：
InputIterator。一个只允许单个向序列读入元素的输入迭代器，前向传递使用operator++和operator*。也可以通过operator==和operator！=检测输入迭代器。这是约束的范围。
OutputIterator。一个只允许单个向序列写入元素的输出迭代器，前向传递使用operator++和operator*。但是，这类OutputIterator不能用operator==和operator！=来进行测试，因为假定仅持续不断地向目的文件发送元素，而无需判定是否到达了目的文件的结束标志。也就是说，OutputIterator涉及的容器可以持有无限个数的对象，而不需要结尾检查。这一点非常重要，因此OutputIterator可以与ostream（通过ostream_iterator）一起使用，同时也普遍使用“插入”迭代器（它是back_inserter（）返回的迭代器类型）。
在相同范围的序列内，没有方法同时确定多个InputIterators或OutputIterators点，因此也就没有办法一起使用这样的迭代器。仅用迭代器来支持istream和ostream，使用InputIterator和OutputIterator就会产生理想的效果。同时也要注意，使用InputIterators或OutputIterators的算法对可接受的迭代器类型做最弱的限制，这意味着当遇到InputIterator或OutputIterator作为STL算法模板参数时，可以使用任意“更复杂”的迭代器类型。
ForwardIterator。因为仅仅可以从InputIterator中读和向OutputIterator中写，不能用它们中的任何一个来同时读和修改某个范围的数据元素，对这样的迭代器只能解析一次。使用ForwardIterator，这些限制就放松了；仍然仅用operator++前向移动，但是可以同时进行读和写，并且可以在相同的范围内比较这些迭代器是否相等。因为前向迭代器可以同时读和写，可以用它来取代InputIterator或OutputIterator。
BidirectionalIterator。实际上，这是一个也可以进行后向移动的ForwardIterator。也就是说，BidirectionalIterator支持ForwardIterator所做的全部操作，而另外还增加了operator—运算。
RandomAccessIterator。这种迭代器类型支持一个常规指针所做的全部运算：可以通过增加和减少某个整数值，来向前和向后跳跃移动（不是每次只移动一个元素），还可以用operator[]作为下标索引，可以从一个迭代器中减去另一个迭代器，也可以用operator＜，operator＞来比较迭代器看哪个更大等等。如果要实现一个排序程序或其他类似的工作，随机存取迭代器是创建一个有效率的算法所必需的。
本章后面的算法描述中，使用的模板参数类型名由列出的迭代器类型（有时附加‘1’或‘2’来区分不同的模板参数）组成，同时也包括其他的参数，通常是函数对象。
当描述传递给运算的元素组时，经常使用数学上“范围”记号。即方括号表示“包括边界点”，圆括号表示“不包括边界点”。当使用迭代器时，要靠指向开始元素的迭代器和指向超越最后一个元素的“超越末尾的”迭代器来决定一个范围。由于根本就没有使用超越末尾的元素，决定这样一对迭代器的范围可以表示成[first, last），这里first是指向开始元素的迭代器，last是超越末尾的迭代器。
大多数教材和对STL算法的讨论都根据它们副作用的大小来组织算法的先后顺序：非变异（non-mutating）算法在作用域范围内不对元素进行改变，变异（mutating）算法改变元素，等等。这些描述基于主要的基础行为或算法的实现—也就是基于设计者的观点。在实际使用中，用户会发现这种分类没用，因此应该根据要解决的问题来组织算法：当你查找某个元素或元素集合时，是不是对每个元素都执行一个运算、计算元素个数并且更新元素等等？这应该有助于更容易发现要求的算法。
如果在函数的声明前面没看到一个如＜utility＞或＜numeric＞的头文件，那么它就应该出现在＜algorithm＞中。同样地，所有的算法都在名字空间std中。
6.3.1 实例创建的支持工具
创建一些基本的工具来测试算法是很有用的。在这些例子中，将使用前面在Generators.h中涉及的发生器以及下面出现的这些内容。
显示一个序列是经常要做的工作，这里有一个函数模板用来打印任意一个序列，它不考虑序列中包含的数据类型：
在默认的情况下，以一个换行符（“n”）作为分隔符，这个函数模板向cout输出，但可以通过修改默认参数来改变它。同时也可以在输出的开头打印一个信息。因为print（）使用copy（）算法经由ostream_iterator向cout发送对象，ostream_iterator必须知道它正在打印的对象的类型，该对象的类型由传递过来的迭代器的value_type成员推断而来。
std：iterator traits模板能够使print（）函数模板处理由任意迭代器类型限定的序列。由标准容器如vector返回的迭代器类型定义了一个嵌套类型value_type，它代表元素的类型。但是当使用数组时，迭代器仅仅只是指针类型，因而不能有嵌套类型。为了支持标准库中与迭代器有关联的使用便利的类型，std：iterator traits为指针类型提供了下面的半特化：
这样就使该模板可获得经由类型名value_type指明的元素类型（即T）。
稳定排序和不稳定排序
对于很多经常移动序列中元素的STL算法而言，有序列的稳定再排序和不稳定再排序之分。就比较函数而言，一个稳定的排序保持相等元素的原始相对顺序。例如，考虑序列{c（1），b（1），c（2），a（1），b（2），a（2）}。在算法中是根据字母来检查这些元素的相等性，但是它们的数字显示怎样在序列中出现（谁在前，谁在后？）。如果排序（例如），对这个序列使用不稳定的排序，就不能保证相同字母间的特定顺序，所以可能以{a（2），a（1），b（1），b（2），c（2），c（1）}结束。然而，如果使用稳定的排序，就会得到{a（1），a（2），b（1），b（2），c（1），c（2）}。STL的sort（）算法使用的是快速排序的一个变种，因此是不稳定的，但是STL也提供稳定的排序算法stable sort（）。[1]
为了证明对一个序列进行重新排序的算法是稳定性算法还是不稳定性算法，我们需要一些方法来保持对元素原始位置的跟踪。下面是一种保持跟踪特殊对象原始出现顺序的string对象，它用static map对从NString到Counters进行映射。这样每个NString包含一个occurrence字段，用来表示在NString中发现的顺序。
通常使用map容器来将一个与字符串一起出现的数字关联起来，但直到第7章才会讨论映射的问题，因此在这里用成对的vector来代替映射。在第7章读者将会看到大量类似的例子。
执行有秩序的升序排序必须的运算符只有NString：operator＜（）。同时还提供降序的排序操作符operator＞（），这样greater模板就能调用它了。
6.3.2 填充和生成
这些算法能够自动用一个特定值来填充（容器中的）某个范围的数据，或为（容器中的）某个特定范围生成一组值。“填充（fill）”函数向容器中多次插入一个值。“生成（generate）”函数使用如前面提到过的发生器来产生插入到容器中的值。
fill（）对[first, last）范围内的每个元素赋值value。fill_n（）对由first开始的n个元素赋值value。
generate（）为[first, last）范围内的每个元素进行一个gen（）调用，可以假定为每个元素产生一个不同的值。generate_n（）对gen（）n调用n次，并且将返回值赋给由first开始的n个元素。
程序举例
下面的例子对vector进行填充和生成。同时也显示了print（）的使用：
vector＜string＞用预定义的大小来创建。因为已经为vector中所有string对象创建了存储空间，fill（）可以用它的赋值操作对vector中的每个空间赋“howdy”的一个拷贝。同时，用空格来取代默认的换行符分隔符。
没有给定第2个vector＜string＞v2的初始大小，因此必须使用back_inserter（）来添加新元素，而不是试图对现有位置赋值。
除了用一个发生器来代替常量值以外，generate（）和generate_n（）函数与“填充”函数有相同的形式。在这里，这两个发生器都演示了它们的功能。
6.3.3 计数
所有的容器都含有一个成员函数size（），它可以告之该容器包含有多少个元素。size（）的返回类型是迭代器的difference_type[2]（通常是ptrdiff_t），下面我们用Integral Value表示。下面的两个算法可以满足一定标准的对象计数。
在这个算法中，产生[first, last）范围内其值等于value（当用operator==测试时）的元素的个数。
这个算法产生[first, last）范围内能使pred返回true的元素的个数。程序举例
这里，用随机字符（包括一些重复的字符）填充vector＜char＞v。set＜char＞由v来初始化，因此它仅持有v中代表的各个字母中的一个。这个set对显示的所有字符的实例进行计数：
count_if（）算法通过对所有的小写字母计数来进行演示；用bind2nd（）和greater函数对象模板创建判定函数。
6.3.4 操作序列
这些都是有关移动序列的算法。
使用赋值，从范围[first, last）复制序列到destination，每次赋值后都增加destination。这本质上是一个“左混洗（shuffle-left）”运算，所以源序列不能包含目的序列。由于使用了赋值操作，因此不能直接向空容器或容器末尾插入元素，而必须把destination迭代器封装在insert_iterator里（在与容器发生联系的情况下，典型地使用back_inserter（）或inserter（））。
这个算法如同copy（）一样，但是以相反的顺序复制元素。这本质上是“右混洗（shuffle-right）”运算，而且如同copy（）一样，源序列不能包含目的序列。将源范围[first, last）序列复制到目的序列，但第1个目的元素是destinationEnd-1。这个迭代器在每次赋值后减少。目的序列范围的空间必须已经存在（允许赋值），而且目的序列范围不能在源序列范围之内。
这个函数的两种形式都倒置了范围[first, last）。reverse（）倒置原序列范围的元素，reverse copy（）保持原序列范围元素顺序不变，而将倒置的元素复制到destination，返回结果序列范围的超越末尾（past-the-end）的迭代器。
通过交换对应的元素来交换相等大小两个范围的内容。
该算法把[first, middle）范围中的内容移到该序列的末尾，并且将[middle, last）范围中的内容移到该序列的开始位置。使用rotate（）在适当的位置执行交换；使用rotate_copy（）不改变原始序列范围，且将轮换后（rotated）版本的元素复制到destination，返回结果范围的超越末尾的迭代器。注意，需要使用swap_ranges（）时，两个范围的大小是完全相等的，但“轮换”函数不是这样。
在这些算法中，排列（permutation）是一组元素的一种独一无二的排序。如果有n个元素，就会有n！（n的阶乘）种不同的元素的组合。所有的这些组合都可以概念化地以词典编纂（像字典一样）的顺序对序列进行排序，这样就产生了一种“后继（next）”和“前驱（previous）”排列的概念。因此无论范围内当前元素的顺序是什么样，在排列的序列中都有一个不同的“后继”和“前驱”的排列。
next_permutation（）和prev_permutation（）函数对元素重新排列成后继的或前驱的排列，如果成功则返回true。如果没有多个“后继”排列，元素以升序排序，next_permutation（）返回false。如果没有多个“前驱”排列，元素以降序排序，previous_permutation（）返回false。
具有StrictWeakOrdering参数的函数形式用binary_pred来执行比较，而不是operator＜。
这个函数随机地重排范围内的元素。如果用随机数发生器，它会产生均匀的分布结果。第1种形式使用内部随机数发生器，第2种使用用户提供的随机数发生器。对于正数n发生器必须返回一个在[0，n）范围内的值。
在这些算法中，“划分”函数将满足pred的元素移到序列的开始位置。迭代器指向其返回元素位置，该元素是超越这些元素中的最后一个（对于以满足pred的元素为开始的子序列，“末尾”迭代器有效）。这个位置通常称为“划分点（partition point）”。
使用partition（），在函数调用后，每个结果子序列的元素顺序并没有被指定，但是用stable_partition（），划分点前后这些元素的相对顺序与划分处理前相同。
程序举例
这里给出了序列运算的演示：
观察这个程序结果的最好方法是运行该程序。（也可以将结果重新输出到一个文件中。）
vector＜int＞v1初始化为一个简单的升序序列，并且打印这个序列。读者将会看到copy_backward（）的效果（复制到v2，v2与v1相同大小）与普通的复制相同。再一次强调，copy backward（）与copy（）做相同的工作—只是以相反的顺序操作。
reverse_copy（）实际上创建一个相反顺序的复制，reverse（）在适当的位置执行颠倒操作。接下来，swap_ranges（）将颠倒序列的上半部分和下半部分进行交换。范围可以比整个vector的子集小，只要它们大小相等就可以。
rotate（）是重新创建一个升序序列的演示，它通过多次交换v1的三分之一来完成排序工作。第2个rotate（）例子使用了字符且每次仅交换两个字符。通过这个例子，也展示了STL算法和print（）模板的灵活性，因为与使用其他任意类型一样，可以很容易地使用char数组。
为了演示next_permutation（）和prev_permutation（），用全部n！（n的阶乘）种组合来排列“abcd”四个字母的集合。从输出结果中可以看到，排列遵循严格的定义顺序（即排列是确定性的处理）。
random_shuffle（）的一个快速演示是将其应用到一个string，并且看结果是什么。因为string对象含有可以返回合适迭代器的begin（）和end（）成员函数，很多STL算法都可以很容易地使用它。同时这里也使用了char型数组。
最后，用NString数组演示了partition（）和stable_partition（）。读者将会注意到，总计的初始化表达式使用的是char型数组，但NString含有一个char*的构造函数，它能自动调用。
从输出结果中可以看到使用不稳定的划分，对象能正确地“被划分”在划分点之上和之下，但不是以特定的顺序进行；反之用稳定的划分则保持原始的顺序。
6.3.5 查找和替换
所有这些算法都用来在某个范围内查找一个或多个对象，该范围由开始的两个迭代器参数定义。
这个算法在某个范围内的序列元素中查找value。返回一个迭代器，该迭代器指向在范围[first, last）内value第1次出现的位置。如果value不在范围内，find（）返回last。这是线性查找（linear search）；也就是说，从范围的起始点开始，对每个连续的元素依次进行检查，而不对元素的顺序路径做任何假设。相反，binary_search（）（在后面定义）是在一个已经有序的序列上工作，因此能够更快地进行查找。
这个算法如同find（）一样，find_if（）在指定的序列范围内执行线性查找。然而，代替查找value, find_if（）寻找一个满足pred的元素，当查找到这样的元素时Predicate pred返回true。如果不能找到这样的元素则返回last。
如同find（）一样，这些算法在指定的序列范围内执行线性查找。但不是仅查找一个元素，而是查找两个邻近的相等元素。函数的第1种形式查找两个相等的元素（通过operator==）。第2种形式查找两个邻近的元素，当找到这两个元素并一起传递给binary_pred时，产生true结果。如果找到这样的一对元素，则返回指向两个元素中第1个元素的迭代器；否则返回last。
如同find（）一样，上面这两个算法也在指定的序列范围内执行线性查找。这两种形式都是在第2个范围内查找与第1个范围内的某个元素相等的元素。第1种形式使用operator==，第2种形式使用提供的判定函数。在第2种形式中，第1个范围序列的当前元素成为binary_pred的第1个参数，第2个范围序列内的元素成为binary_pred的第2个参数。
这些算法检查第2个序列范围是否出现在第1个序列的范围内（顺序也完全一致），如果是则返回一个迭代器，该迭代器指向在第1个范围序列中第2个范围序列出现的开始位置。如果没有找到就返回last1。第1种形式测试使用operator==，第2种形式检测被比较的每对元素是否能使binary_pred返回true。
这些算法的形式和参数如同search（），查找第2个范围的序列是否在第1个范围内作为子集出现，但是search（）查找该子集首先出现的位置，而find_end（）则查找该子集最后出现的位置，并且返回指向该子集的第一个元素的迭代器。
这些算法在[first, last）范围内查找一组共count个连续的值，这些值都与value相等（在第1种形式中），或是当将所有这些与value相同的值传递给binary_pred时返回true（在第2种形式中）。如果不能找到这样的一组数值就返回last。
这些算法返回一个迭代器，该迭代器指向范围内“最小的”值首次出现的位置（如下面的解释—范围内可能会多次出现这个值）。如果范围为空则返回last。第1种版本用operator＜执行比较，且返回值为r，其意义是：对于范围[first, r）中每个元素e，e＜r都为假。第2种版本用binary_pred比较，且返回值为r，其意义是：对于范围[first, r）中每个元素e, binary_pred（e，r）都为假。
这些算法返回一个迭代器，该迭代器指向范围内最大值首次出现的位置。（范围内可能会多次出现最大值。）如果范围为空返回last。第1种版本用operator＜执行比较，且返回值为r，其意义是：对于范围[first, r）中每个元素e，r＜e都为假。第2种版本用binary_pred执行比较，且返回值为r，其意义是：对于范围[first, r）中每个元素e, binary_pred（r，e）都为假。
在这些算法中，每一种“替换”形式都从头至尾在范围[first, last）内进行查找，找到与标准匹配的值并用new_value替换它们。replace（）和replace_copy（）都是仅仅查找old_value并对其进行替换；replace_if（）和replace_copy_if（）查找满足判定函数pred的值。函数的“复制”形式不修改原始范围，而是将作为替代的一个副本赋给result，更换它的值（每次赋值后增加result）。
程序举例
为了提供简单的可视结果，这个例子运算int型的vector。再强调一次，并不是将每一个算法的所有版本都展现出来。（一些意义很明显的算法被略去了。）
这个例子以两个判定函数开始：PlusOne是一个二元判定函数，如果第2个参数等于第1个参数加1则返回true；MulMoreThan也是一个二元判定函数，如果第1个参数与第2个参数的乘积大于存储在对象中的值则返回true。这些二元判定函数在例子中用来进行测试。
在main（）中，创建一个数组a并将其提供给vector＜int＞v的构造函数。vector是查找和替换行动的目标，注意这里有很多重复元素—它们由一些查找/替换程序发现。
第1个测试演示find（），在v中发现值4。返回值是指向4的第1个实例的迭代器，如果没有找到要查找的值，返回值指向输入范围的末尾（v.end（））。
find_if（）算法使用了一个判定函数来决定是否找到了正确的元素。在本例中，用一个动态的greater＜int＞（即，“查看第1个int型参数是否大于第2个参数”）和固定的第2个参数8来创建一个执行中的判定函数bind2nd（）。因此，如果v中的值大于8则返回真。
因为在许多情况下v中会出现两个相同的相邻对象，所以设计adjacent_find（）测试来找到它们。查找从序列的开始位置出发，然后进入一个while循环，以便确定迭代器it没有到达该输入序列的末尾（这意味着不能再找到更多匹配的元素）。对于找到的每个匹配，循环打印这些匹配的元素并且执行下一个adjacent find（），这时就使用it+1作为第1个参数（用这种方式在三元组中能够找到两对匹配的元素）。
观察while循环，想一想如何能够使它的工作完成的更加精巧，如下所示：
这个程序正是我们之前尝试的方式。但是该程序在任何编译器上都不可能得到期望的输出结果。这是因为对在循环内表达式中出现增1时的情况没有做出任何可靠的保证。
下一个测试使用了以PlusOne判定函数作为参数的adjacent find（），这个判定函数PlusOne能发现序列v中所有的下一个数比前一个数改变了1的元素位置。同样，采用while方法也能找到所有这样的情况。
算法find_first_of（）需要另外一个对象范围来辅助，这由数组b提供。由于find_first of（）中的第1个和第2个范围由不同的模板参数控制，正如所见，这两个范围可以引用两个不同类型的容器。find_first_of（）的第2种形式也进行了测试，使用了PlusOne。
search（）算法精确地在第1个序列范围内找到了第2个范围序列，并且它们的元素具有相同的顺序。search（）的第2种形式使用了一个判定函数，该形式的典型应用是查找那些定义相等的序列，但也有可能进行更加有趣的查找—在这里，PlusOne判定函数找到的范围是{4，5，6}。
find_end（）测试发现了在整个序列的最后出现的{11，11，11}。为了显示它实际上已经找到了最后出现的这个子集，从迭代器it指向的位置开始打印v串的剩余部分。
第1个search n（）测试寻找7的3个副本，找到它们并且打印出来。当使用search n（）的第2种版本时，判定函数的出现一般意味着使用它来判定两个元素间的相等性，但是也可以有一些选择的自由。并且使用一个函数对象，这个函数对象是用15（在本例中）去乘序列中的值，并且检查它们是否大于100。也就是说，search n（）检测要做的是“找到6连续的那些值，当被15乘时，每个产生的数大于100。”这不能精确地描述读者平常期望做的那些工作，但是却可以为下次遇到不寻常的查找问题时提供一些办法。
min element（）和max element（）算法很直观，但是看上去有些怪异。函数似乎是用一个“*”来引用。实际上，返回的迭代器被释放掉以便产生打印的值。
为了测试替换，首先使用replace_copy（）（这样不会修改原始vector）以值47来替换所有值为8的元素。注意，用一个空的vector v2对back_inserter（）进行调用。为了演示replace_if（），用标准模板greater_equal连同bind2nd创建一个函数对象，用-1替换所有值大于等于7的元素。
6.3.6 比较范围
下面这些算法提供比较两个范围的方法。乍看起来，这些算法执行的运算类似search（）函数。可是，search（）查找的是第2个序列出现在第1个序列中的位置，而equal（）和lexicographical_compare（）所做的只是进行两个序列的比较。另一方面，mismatch（）比较两个序列在哪里停止同步比较，这两个序列必须有完全相同的长度。
在这两个函数中，[first1，last1）表示的第1个范围是一个典型的表示方法。第2个范围开始于first2，但是没有“last2”因为第2个范围的长度由第1个范围的长度来决定。如果两个范围完全相同（有相同的元素和相同的顺序），equal（）函数返回真。在第1种情况中，由operator==执行比较，在第2种情况中，由binary_pred来决定两个元素是否相同。
这两个函数决定第1个范围是否“字典编纂顺序的小于（lexicographically less）”第2个范围。（如果范围1小于范围2返回true，否则返回false。）字典编纂顺序的比较（lexicographical comparison）或称为“字典（dictionary）”比较，意味着比较的顺序等同于按字典规则建立字符串的顺序：每次比较一个元素。如果第1个元素不同，第1个元素就决定了两个字符串比较的结果，但是如果相同，算法移到下一个元素继续检查它们，如此下去直到遇到不匹配的那对元素为止。在这个点上，检查这对元素，如果范围1序列中的这个元素小于范围2序列中的相应元素，lexicographical_compare（）返回true；否则返回false。如果用能得到的所有方法从头至尾扫描一个范围或另一个范围（本算法中范围的长度可以不同），都没有发现不相等的地方，范围1不小于范围2，因此函数返回false。
如果两个范围的长度不同，按字典编纂顺序，一个范围内缺少的元素起到“领先于（precede）”另一个范围内存在的元素的作用，因此“abc”领先于“abcd”。如果算法执行到一个范围的结尾，还没有找到不匹配的元素对，这时短的范围领先（按字典编纂顺序领先，即小）。在这种情况下，如果短的范围是第1个范围，则结果是true，反之是false。
在函数的第1种版本中，由operator＜执行比较，在第2种版本中，使用判定函数binary_pred。
这些算法如同在equal（）中一样，进行比较的两个范围的长度完全相同，因此仅需要第2个范围的first迭代器，第1个范围的长度可以用来做第2个范围的长度。这个函数的功能与equal（）正好相反，equal（）仅比较两个范围是否相同，mismatch（）告诉比较从哪里开始不同。为了完成这一工作，必须知道以下几点（1）第1个范围内出现不匹配的元素的位置；（2）第2个范围内出现不匹配的元素的位置。将两个迭代器一起装入一个pair对象并返回。如果没有出现不匹配，返回值是与第2个范围结合在一起的超越末尾的迭代器last1。pair模板类是一个struct，该struct含有两个用成员名first和second表示的元素，在＜utility＞头文件中定义。
如同在equal（）中一样，第1个函数测试相等性使用operator==，而第2个使用binary_pred。
程序举例
因为标准C++string类构造得如同一个容器（它含产生类型string：iterator的对象成员函数begin（）和end（）），可以方便地用来创建字符范围序列来测试STL比较算法。然而，需要注意的是，string有一个相当完整的属于自己的运算集，因此在使用STL算法执行运算之前，需要查看一下string类。
注意，s1和s2的惟一不同点是：s2的“Test”中的大写字母“T”。比较s1和s2的相等性产生true。不出所料，因为大写字母“T”，s1和s2不相等。
为了理解lexicographical compare（）测试的输出结果，要记住两件事：首先，比较是按一个字母接着一个字母的顺序执行的；第二，现在C++编译系统的操作平台上，大写字母字符“领先于”小写字母字符。在第1个测试中，是s1与s1进行比较。这当然是完全相等。以字典编纂顺序进行比较，不会产生一个序列小于另外一个序列的结果（这是比较要寻找的结果），因此结果是false。第2个测试是问“s1领先于s2吗”？当比较进行到“test”中的第1个字符‘t’时，发现s1中的小写字母字符‘t’“大于”s2中的大写字母字符“T”，所以答案是false。但是，如果测试要看看s2是否领先于s1，答案是true。
为了更进一步地检测字典编纂顺序比较，本例中的下一个测试再次比较s1和s2（前面的比较返回false）。这次重复这个比较，每次通过循环减去s1（首先将s1复制到s3）末尾的一个字符，直到测试结果返回true。读者将会看到些什么？看到的是：只要从s3（s1的副本）中依次减到大写字母“T”，此时，则两个序列从开始一直到这一点都完全相等，不再进行计算。因为s3比s2短，s3字典编纂顺序领先于s2。
最后的测试使用mismatch（）。为了得到返回值，现在创建合适的pair p，用第1个范围的迭代器类型及第2个范围的迭代器类型（在本例中，都是string：iterator）构造模板。为了打印该函数产生的结果，函数中第1个范围的不匹配迭代器是p.first，第2个范围的迭代器是p.second。在这两种情况中，从函数不匹配的迭代器开始到范围的末尾来打印该范围序列，所以可以准确地看到哪里是迭代器指出的点。
6.3.7 删除元素
因为STL的通用性，这里对删除的概念有一点限制。既然在STL中仅能通过迭代器“删除”元素，而迭代器可以指向数组、vector、list等，那么试图销毁正在被删除的元素和改变输入范围[first, last）的大小是不安全或是不合理的。（例如，一个已存在数组不能改变它的大小。）因此取而代之，STL“删除”函数重新排列该序列，就是将“已被删除的”元素排在序列的末尾，“未删除的”元素排在序列的开头（与以前的顺序相同，只是减去被删除的元素—也就是说，这是一个稳定的操作）。然后函数返回一个指向序列的“新末尾”元素的迭代器，这个“新末尾”元素是不含被删除元素的序列的末尾，也是被删除元素序列的开头。换句话说，如果new_last是从“删除”函数返回的迭代器，则范围[first, new_last）是不包含任何被删除元素的序列，而范围[new_last,last）是被删除元素组成的序列。
如果想通过更多的STL算法来简单地使用序列，并把那些已被删除的元素包括在序列内，可以仅用new_last作为新的超越末尾的迭代器。但是，如果使用一个可以调整大小的容器c（不是一个数组），当想从容器中消除被删除的元素时，可以使用erase（）来完成，例如：
也可以使用属于所有标准序列容器的resize（）成员函数（更多关于此问题的内容将在第7章介绍）。
remove（）的返回值是称为new_last的迭代器，而erase（）则从c中真正删除掉所有的要被删除的元素。
[new_last, last）中的迭代器是能解析的，但是那些元素值未被指定，应该不再使用。
这里介绍的每一种“删除”形式都从头至尾遍历范围[first, last），找到符合删除标准的值，并且复制未被删除的元素覆盖已被删除的元素（因此可有效地删除元素）。未被删除的元素的原始排列顺序仍然保持。返回值是指向超越范围末尾的迭代器，该范围不包含任何已被删除的元素。这个迭代器指向的元素的值未被指定。
“if”版本的删除把每一个元素传递给判定函数pred（），来决定是否应该删除。（如果pred（）返回true，则删除该元素。）“copy”版本的删除不需要修改原始序列，而取而代之是复制未被删除的值到一个开始于result的新范围，并返回指向新范围的超越末尾的迭代器。
在这些算法中，“unique”函数的每一种版本都从头至尾遍历范围[first, last），找到相邻的相等值（即副本），并且通过复制覆盖它们来“删除”这些副本。未被删除的元素的原始顺序仍然保持不变。返回值是指向该范围的超越末尾的迭代器，该范围相邻副本已被删除。
因为要删除的只是相邻的副本，因此如果有可能的话，在调用“unique”算法之前，调用sort（），这样就能保证全部的副本都被删除掉。
对于输入范围内的每个迭代器的值i，包含在binary_pred调用版本中：
如果返回值是true，则认为*i是一个副本。
“copy”版本不改变原始序列，取而代之复制未被删除的值到一个开始于result的新范围，并返回指向新范围的超越末尾的迭代器。
程序举例
这个例子给出了“remove”和“unique”函数工作的一个演示。
字符串v是一个由随机产生的字符填满的字符容器。每个字符在remove语句中都被使用，但是每次都显示全部的字符串v，因此在得到结束点以后（存储在cit中），就可以看到该范围的剩余部分到底发生了什么变化。
为了演示remove_if（），在函数对象类IsUpper中调用标准C库函数isupper（）（在＜cctype＞中），将一个对象作为一个判定函数传递给remove_if（）。仅当字符是大写的时候返回true，因此只保留小写字符。在这里，在print（）的调用中使用了范围的末尾作为参数，因此仅显示保留的元素。remove（）和remove_if（）的复制形式没有演示，因为它们是非复制版本的一个简单变种，无需例子就应该会使用。
先对小写字母的序列进行排序，为测试“unique”函数做准备。（如果该序列未排序，则“unique”函数就不能被定义，但这大概并不是读者想要的。）首先，unique_copy（）使用默认的元素比较将序列中独一无二的元素放入一个新的vector中，然后再使用含有判定函数的unique（）形式。判定函数嵌入到函数对象equal_to（）中，它与默认的元素比较产生相同的结果。
6.3.8 对已排序的序列进行排序和运算
STL算法的一个重要种类就是必须对已排好序的范围序列进行运算。STL提供了大量独立的排序算法，分别对应于稳定的、部分的或仅是规则的（不稳定的）排序。说也奇怪，只有部分排序有复制的版本。如果使用其他排序算法并且需要在一个副本上工作，那么就需要在排序前由用户自己来完成复制工作。
对于一个已经排好序的序列，可以在该序列上执行多种运算，包括从该序列中找出指定的某个元素或某组元素，到与另外的一个已排序的序列进行合并，或像数学集合一样来运算该序列等等。
对已排好序的序列进行包括排序或运算的每个算法都有两种版本。第1种版本使用对象自己的operator＜来执行比较，第2种版本用operator（）（a, b）来决定a和b的相对顺序。除此之外没有什么不同之处，所以不会在每个算法的描述中都指出这个不同点。
1.排序
排序算法需要由随机存取的迭代器来限制序列的范围，比如vector或deque。list容器有自己的嵌入sort（）函数，因为它仅提供双向的迭代。
这些算法将[first, last）范围内的序列按升序顺序排序。第1种形式使用operator＜，第2种形式使用提供的比较器对象来决定顺序。
这些算法将[first, last）范围内的序列按升序顺序排序，保持相等元素的原始顺序。（假设元素可以是相等的但不是相同的，这一点很重要。）
这些算法对来自[first, last）范围中的一定数量的元素进行排序，这些元素可以放入范围[first, middle）中。排序结束，在范围[middle, last）中其余的那些元素并不保证它们的顺序。
这些算法对来自[first, last）范围中的一定数量的元素进行排序，这些元素可以放入范围[result_first, result_last）中，并且复制这些元素到[result_first, result_last）。如果范围[first, last）比[result_first, result_last）小，则使用较少的元素。
这些算法如同partial_sort（），nth_element（）部分地处理（排列）范围内的元素。但是，它比partial_sort（）要“少处理”得多。nth_element（）惟一保证的是无论选择什么位置，该位置都会成为一个分界点。范围[first, nth）内的所有元素都会成对地满足二元判定函数（通常默认的是operator＜），而范围（nth, last]内的所有元素都不满足该判定。但是，任何一个子范围都不会是一个以特定的顺序排好序的序列，这不像partial_sort（），它的第1个范围已排好序。
如果需要的是很弱的排序处理（例如，决定中值、百分点等等），这个算法要比partial_sort（）快得多。
2.在已排序的范围中找出指定元素
一旦某个范围被排好序，就可以在范围内使用一系列运算来查找元素。在下面的函数中，总是存在有两种形式。一种是假定内在的operator＜来执行排序，第2种运算符是使用一些其他的比较函数对象来执行排序。必须使用与执行排序相同的比较方法来定位元素；否则，结果不确定。另外，如果试图在未排序的范围上使用这些函数，结果将不可预料。
这些算法告诉用户是否value出现在已排序的范围[first, last）中。
这些算法返回一个迭代器，该迭代器指出value在已排序的范围[first, last）中第1次出现的位置。如果value没有出现，返回的迭代器则指出它在该序列中应该出现的位置。
这些算法返回一个迭代器，该迭代器指出在已排序的范围[first, last）中超越value最后出现的一个位置。如果value没有出现，返回的迭代器则指出它在该序列中应该出现的位置。
在这些算法中，本质上结合了lower_bound（）和upper_bound（），返回一个指出value在已排序的范围[first, last）中的首次出现和超越最后出现的pair。如果没有找到，这两个迭代器都指出value在该序列中应该出现的位置。
读者可能会惊讶于一个发现，即二分查找（也称折半查找）算法使用一个前向顺序查找的迭代器而不是随机存取的迭代器。（绝大多数对二分查找的解释是使用索引。）记住随机存取迭代器“是（is-a）”向前顺序查找的迭代器，它可以用在后者（向前顺序查找的）指定的地方。如果传递给这些算法之一的迭代器实际上支持随机存取，则使用了有效率的对数时间查找，否则执行的是线性查找。[3]
3.程序举例
下面的例子将输入的每一个单词转化成NString，并且将其加入到vector＜NString＞。然后使用vector来演示各种排序和查找算法。
这个例子使用前面见过的NString类，它存储一个字符串的副本出现的次数。stable_sort（）的调用显示了含相等字符串的对象的原始顺序是如何保存的。同时也可以看到在“部分排序”期间到底发生什么事情（保留的未排序的元素处在非特定的顺序之中）。不存在“部分的稳定排序。”
注意，在nth_element（）的调用中，无论nth元素变成什么（因为URandGen发生器，它可以从一个元素变成另一个元素），其前面的元素总是小于它，后面的元素大于它，此外这些元素并没有特定的顺序。由于URandGen发生器不存在副本，但是如果使用允许副本的发生器，将会看到nth元素以前的元素小于等于该nth元素。
这个例子也演示了全部的3个二分查找算法。同介绍过的一样，lower_bound（）用来查找序列中第1个等于给定关键字值的元素，upper_bound（）指向个最后一个符合条件元素的下一元素，而equal_range（）将两个结果作为一对数据返回。
4.合并已排序的序列
如同前面一样，每个函数的第1种形式假定由内在的operator＜执行排序。第2种形式必须使用一些其他比较函数对象执行排序。必须使用与执行排序相同的比较方法来定位元素；否则，结果不确定。另外，如果试图在未排序的序列范围上使用这些算法，结果也会不可预料。
在这些算法中，从[first1，last1）和[first2，last2）中复制元素到result，这样在结果范围的序列以升序的顺序排序。这是一个稳定的运算。
这里假定[first, middle）和[middle, last）是在相同的序列中已排好序的两个范围。合并这两个范围序列到一个结果序列，该结果序列范围[first, last）包含将两个排好序的范围结合成一个有序的范围。
5.程序举例
很容易看到，如果在合并中使用int类型将会发生什么事情。下面的例子同时也强调了算法（以及我们自己定义的print模板）是怎样与数组和容器一起工作的：
在main（）中，不是创建两个独立的数组，而是在数组a中创建两个首尾相连的范围。（这为inplace_merge带来方便。）第1个merge（）的调用把结果放入一个不同的数组b中。为了进行比较，同时也调用set_union（），它与第1个merge（）的调用有相同的标识符及类似的行为，除了它从第2个集合中删除副本。最后，inplace_merge（）将a的两个部分结合到一起。
6.在已排序的序列上进行集合运算
一旦范围已排好序，就可以在其上执行数学集合运算。
在这些算法中，如果[first2，last2）是[first1，last1）的一个子集，返回true。没有任何一个范围要求只持有与另一个范围完全不同的元素，但是如果[first2，last2）持有n个特定值的元素，假如要想使返回结果为true，[first1，last1）也必须同时至少持有n个元素。
这些算法在result范围中创建两个已排序范围的数学并集，返回值指向输出范围的末尾。没有任何一个输入范围要求只持有与另一个范围完全不同的元素，但是，如果在两个输入集合中多次出现某个特定值，结果集合中将包含完全相同的值出现的较大次数。
这些算法在result中产生两个输入集合的交集，返回值指向输出范围的末尾—即在两个输入集合中都出现的数值的集合。没有任何一个输入范围要求只持有与另一个范围完全不同的元素，但是如果某个特定值在两个输入集合中多次出现，结果集合中将包含完全相同的值出现的较小次数。
这些算法在result中产数学上集合的差，返回值指向输出结果范围的末尾。所有出现在[frist1，last1）中，但不在[first2，last2）中出现的元素都放入结果集合。没有任何一个输入范围要求只持有独特的元素，但是如果某个特定值在两个输入集合中多次出现（在集合1中n次，集合2中m次），结果集合将包含这个值的max（n-m，0）个副本。
在result集合构成中，包括：
1）所有在集合1中而不在集合2中的元素。
2）所有在集合2中而不在集合1中的元素。
在这些算法中，没有任何一个输入范围要求只持有独特的元素，但是如果某个特定值在两个输入集合中多次出现（在集合1中n次，集合2中m次），结果集合将包含这个值的abs（n-m）个副本，其中abs（）是取绝对值函数。返回值指向输出结果范围的末尾。
7.程序举例
观察仅使用字符的vector来演示集合运算将更加容易。这些字符是随机产生的，并被排序，但保留了副本，当有了副本时，现在就可以看到集合运算怎样执行。
在v和v2产生、排序和打印之后，通过观察v的全部范围是否包含v的后半部分来测试includes（）算法。如果包括，结果通常应该是真。数组v3保存set union（）、set intersection（）、set difference（）和set symmetric difference（）的输出结果，每一个结果都显示出来，这样读者就可以分析、思考它们，并确信算法正如预想的那样执行。
6.3.9 堆运算
堆是一个像数组的数据结构，用来实现“优先队列”，“优先队列”是一个靠优先权调节检索元素的方式来组织的序列，其中优先权是依据某些比较函数决定的。标准库中的堆运算允许一个序列被视为是一个“堆”数据结构，这通常可以有效地返回最高优先权的元素，而无需全部排序整个序列。
如同“排序”运算一样，每个函数都有两种版本。第1种使用对象自己的operator＜来执行比较；第2种使用另外的StrictWeakOrdering对象的operator（）（a, b）来比较两个对象：a＜b。
这些算法将一个任意序列范围转化成堆。
这些算法向由范围[first, last-1）决定的堆中增加元素*（last-1）。换句话说，将最后一个元素放入堆中合适的位置。
在这些算法中，将最大的元素（在运算前实际上在first中，这是堆定义方式的缘故）放入位置（last-1）并且重新组织剩余的范围，使其仍然在堆的顺序中。如果只是抓取*first，下一个元素就将不是下一个最大的元素；因此，如果想以完全优先队列的顺序保持堆，必须调用pop_heap（）来完成这个运算。
可以将这些算法完成的工作想象为make_heap（）的补充。它使一个以堆顺序排列的序列，转化成普通的排列顺序，这样它就不再是一个堆。这意味着如果调用sort_heap（），将不能再在这个序列范围上使用push_heap（）或pop_heap（）。（当然，你可以使用这些函数，但不会完成任何有意义的工作。）这是个不稳定的排序。
6.3.10 对某一范围内的所有元素进行运算
这些算法遍历整个范围并对每个元素执行运算。它们在利用运算的结果方面有所不同：for_each（）丢弃运算的返回值，而transform（）将每个运算的结果放入一个目的序列（也可以是原始序列）。
在该算法中，对[first, last）中的每个元素应用函数对象f，丢弃每个个别的f应用的返回值。如果f仅是一个函数指针，说明这是典型的与返回值无关；但是，如果f是一个保留某些内部状态的对象，则该对象可以捕获一个返回值，它们结合到一起应用到该范围上。for_each（）的最终返回值是f。
这些算法，如同for_each（）一样，transform（）对范围[first, last）中的每个元素应用函数对象f。但是，不是丢弃每次函数调用的结果，transform（）而是将结果复制（使用operator=）到*result，每次复制后增加result的内容。（result指向的序列必须有足够的存储空间；否则，用一个插入符强迫插入来代替赋值。）
transform（）的第1种形式仅调用了f（first），在这里第1个范围表示一个输入序列。类似地，第2种形式调用f（first1，*first2）。（注意，第2个输入范围的长度由第1个输入范围的长度决定。）这两种情况的返回值都是超越末尾的迭代器，该迭代器指出结果输出范围。
程序举例
因为对容器中的对象做的大部分工作是对所有这些对象应用某个运算，这些都是相当重要的算法，值得为此给出一些例证。
首先，分析for_each（）。它扫描整个范围，依次提取每个元素并把它作为一个参数进行传递，如同调用的任何被授予的函数对象一样。因此，for_each（）执行那些由用户编写的规范的运算。如果想在编译器的头文件中查看for_each（）的模板定义，将会看到下述编码：
下面的例子显示了一些能够扩展这个模板的几种方法。首先，需要一个保持追踪它的对象的类，这样我们就可以知道这些对象被适当地销毁掉：
class Counted对已创建的Counted对象的个数保存一个静态的计数，并且当这些对象被销毁时通知用户[4]。另外，每个Counted对象保存一个char*标识符以便追踪输出更加容易。
CountedVector由vector＜Counted＞派生而来，并且在构造函数中创建一些Counted对象，处理每个想要的char。CountedVector使测试相当简单，如下所示：
显然，在这里有一些事情需要反复多次去做，既然这样，为什么不创建一个算法用delete来删除容器中所有的指针呢？可以使用transform（）来完成这项工作。transform（）优于for_each（）的地方在于transform（）将调用函数对象的结果赋给结果范围，该结果范围实际上是输入范围。这种情况意味着对输入范围的序列进行逐字的转换，因为每个元素是原先值的一个修改。在本例中这个方法尤其有用，因为在对每个指针调用delete后，为其赋安全的零值更加适合。transform（）可以很容易地做到这些：
这里显示了两种方法：使用模板函数或模板化的函数对象。在调用transform（）后，vector包含5个空指针，它更安全因为用它对任何副本delete都是无效的。
有一件事不能做，那就是在遍历中delete每个指针，而没有在函数或对象内部封装对delete的调用。即如下面所做：
这与前面的destroy（）调用有相同的问题：operator delete（）获取一个void*，但是迭代器并不是指针。甚至如果要对它进行编译，得到的将是一系列用来释放存储空间的函数调用。不能得到对a中每个指针都调用delete的效果，然而不会调用析构函数。这显然不是想要的结果，所以需要封装对delete的调用。
在前面的for_each（）的例子中，忽略了算法的返回值。这个返回值是传递给for_each（）的函数。如果这个函数仅是指向一个函数的指针，该返回值并不是很有用，但如果它是一个函数对象那就完全不同了，这个函数对象可能含有内部的成员数据，可以使用这些成员数据来积累关于在for_each（）中见到的所有对象的信息。
例如，考虑一个简单的存货清单模型。每个Inventory对象包含它所代表的产品类型（在这里用单个的字符表示产品项目名称）、该产品的数量以及每种产品的价格。
成员函数取得产品项目的名称，取得并确定相应的数量和价格。o p e r a t o r＜＜向ostream打印出Inventory对象。用一个发生器来创建这些对象，这些对象含有顺序标记的产品项目名及随机的数量和价格。
为了找出产品项目的总数及全部价值，可以使用含有总计数据成员的for_each（）来创建一个函数对象：
InvAccum的operator（）有一个参数，这是for_each（）要求的。当for_each（）遍历某个范围时，获取该范围的每一个对象并将其传递给InvAccum：operator（），它执行计算并保存结果。在这个处理的最后，for_each（）返回InvAccum对象，并打印该InvAccum对象。
使用for_each（）可以对Inventory对象做很多事。例如，for_each（）可以方便地将所有产品的价格增加10%。但是读者会注意到Inventory对象没有办法改变item的值。设计Inventory的程序员认为这是一个好的主意。毕竟，为什么想要改变一个商品的名称？但是在市场上的交易已经决定了要将所有的产品名称改为大写，使得它们看上去与“新的、改进的”产品一样。他们已经做了调研并且决定用新的产品名称来进行促销（好了，为了市场上的交易总需要做一些事情……）。所以这里不使用for_each（），而是使用transform（）：
注意，结果范围与输入范围相同；即，在适当的位置执行转换。
现在假设销售部门需要产生一个特价清单，对每种商品有不同的折扣。原始的清单必须原样保留，并且需要产生任意数量的特价清单。销售部门将为每个新清单提供一个单独的折扣明细表。为了解决这个问题，这里使用transform（）的第2种版本：
给定一个Inventory对象和一个折扣比率，Discounter函数对象产生一个新的含折扣价格的Inventory对象。DiscGen函数对象仅产生随机的从1%到10%之间的折扣值用来进行测试。在main（）中创建两个vector，一个用于Inventory，一个用于折扣。将它们随同Discounter对象传递给transform（），transform（）填充一个新的称为discounted的vector＜Inventory＞对象。
6.3.11 数值算法
这些算法都包含在头文件＜numeric＞中，因为它们主要用来执行数值计算。
第1种形式是一般化的合计，对于由迭代器i指向的[first, last）中的每一个元素，执行运算result=result+i，在这里result是T类型。但是，第2种形式更普遍；它对于范围中从头至尾的每一个元素i应用函数f（result，*i）。
注意transform（）的第2种形式和accumulate（）的第2种形式之间的相似之处。
在这些算法中，计算两个范围[first1，last1）和[first2，first2+（last1-first1））的一个广义内积。用第1个序列中的元素乘以第2个序列中“平行的”元素并对其积进行累加来产生返回值。因此，如果有两个序列{1，1，2，2}和{1，2，3，4}，内积是
返回结果为17。参数init是内积的初始值—可能是0也可能是任何值，这对于空的第1个序列尤其重要，因为它是默认的返回值。第2个序列必须至少要含有与第1个序列一样多的元素。
第2种形式对它的序列应用一对函数。函数op1用来代替加法，而函数op2用来代替乘法。因此，如果对上面的序列应用inner_product（）的第2种版本，结果会是下面的这些运算：
所以，这与transform（）相似，但用执行两个运算来代替一个运算。
这些算法计算一个广义部分和。创建一个新的在result开始的序列。新序列中每个元素都是[first,last）范围中从第1个元素到当前选择的元素之间所有元素的累加和。例如，如果原始序列是{1，1，2，2，3}，产生的结果序列是{1，1+1，1+1+2，1+1+2+2，1+1+2+2+3}，即{1，2，4，6，9}。
在第2种版本中，使用二元函数op代替+运算符，取得累积到那个点的所有的“合计”，并且把它与新值结合起来。例如，对上面的序列使用multiplies＜int＞（）（一种乘法op）作为对象，输出结果是{1，1，2，4，12}。注意，在输入/输出两个序列中，第1个输出结果值始终与第1个输入值相同。
返回值指向输出范围[result, result+（last-first））的末尾。
这些算法计算全部范围[first,last）中的相邻元素的差。这意味着在新序列中，每个元素的值是原始序列中当前元素与前面的元素的差值（第1个值不变）。例如，如果原始序列是{1，1，2，2，3}，结果序列是{1，1-1，2-1，2-2，3-2}，即{1，0，1，0，1}。
第2种形式使用二元函数op代替‘-’运算符执行“求差”。例如，如果对序列使用multiplies＜int＞（）作为函数对象（即用“乘法”代替“减法”），输出结果是{1，1，2，4，6}。
返回值指向输出范围[result, result+（last-first））的末尾。
程序举例
这个程序在整型数组上测试＜numeric＞头文件中所有的算法的两种形式。读者将会注意到，在程序例子提供的函数或函数群的形式测试中，这些函数对象被使用的形式是一致的，而使用形式一致则产生相同的结果，因此结果是完全相同的。这里也演示了更加清晰的运算，该运算继续下去就是如何替换用户自己的运算。
注意，inner_product（）和partial_sum（）的返回值是结果序列的超越末尾的迭代器，因此作为print（）函数中的第2个迭代器。
因为每个函数的第2种形式允许用户提供自己的函数对象，所以仅函数的第1种形式是纯“数值的”。读者可以用inner_product（）做很多能想得到的非直观数值的事情。
6.3.12 通用实用程序
最后，这里还有与其他的算法一起使用的一些基本工具；用户自己可能会，也可能不会直接使用这些工具。
在本章前面描述并使用过这些工具。pair是一个简单的将两个对象（可能不同类型的对象）封装成一个对象的方法。当需要从一个函数返回多个对象时使用它是很典型的情况，但是也可以用来创建一个持有pair对象的容器，或将多个对象作为一个参数进行传递。通过p.first和p.second来访问指定的元素，这里p是pair对象。例如，本章中描述的equal_range（）函数，作为迭代器的pair来返回结果。可以直接insert（）一个pair到map或multimap中；对于这些容器来说pair是value_type。
如果想“在执行中”创建一个pair，典型的方法是使用模板函数make_pair（），而不是显式地构造一个pair对象。make_pair（）会自动推断出它接收到的参数的类型，这样即减轻程序员打字的负担，也增加了程序的健壮性。
该算法计算first与last之间的元素个数。更准确地说，它返回一个整数值，这个整数表示在frist等于last之前它必须增加的次数。在这一处理过程中不会发生解析迭代器的现象。
（From＜iterator＞）
根据n的值前向移动迭代器i的位置。（如果迭代器是双向的，也可以根据n的负值向后移动。）这个算法意识到，对不同类型的迭代器应该采用不同的方法，而它使用的都是最有效的方法。例如，对随机迭代器可以用普通的算术（i+=n）直接增加，而双向迭代器必须增加n次。
这些函数用来为给定的容器创建迭代器，以便向容器中插入元素，而不是用operator=覆盖容器中已存在的元素（这是默认的行为）。每种类型的迭代器对插入使用不同的运算：back_insert_iterator使用push_back（），front_insert_iterator使用push_front（），而insert_iterator使用insert（）（因此可以与关联式容器一起使用，而另外两种可以与顺序容器一起使用）。这些细节将在第7章中介绍。
在这些算法中，返回两个参数中较小的一个，或如果两个参数相等则返回第1个参数。第1种版本用operator＜执行比较，而第2种版本将两个参数传递给binary_pred来执行比较。
这些算法与min（）很像，但是返回两个参数中较大的一个。
使用赋值的方法来交换a和b的值。注意，所有的容器类都使用特化的swap（）版本，这比通用的版本要更有效得多。
iter_swap（）函数交换它涉及的两个参数的值。
[1]stable_sort（）使用归并排序，归并排序是稳定排序，但是在平均情况下比快速排序慢。
[2]在第7章中我们将详细讨论迭代器。
[3]通过读取tag，算法能够决定迭代器的类型，这将在第7章讨论。
[4]在这个例子中我们忽略了拷贝构造函数和赋值操作，因为没有使用它们。
